[SGU138]构造法**

【题目大意】 有n个人下棋,每次有两个人下,赢者留下再比(可以与刚下败的人)。给出每个人下的次数,要求出一种可行方案,输出每次比赛的过程,赢者放在第一列,败者放在第二列。

【算法分析】传说中的构造。。。看了别人的还不懂,然后再看了程序才懂= =
就是把那些人按出场的次数从大到小排序,然后让前面的人尽量赢,然后再按顺序填掉剩下的表就行了。
我看的是这个:http://www.cppblog.com/schindlerlee/archive/2010/01/27/106503.html?opt=admin
但是值得注意的是最后他说的那句剩下的随便填是绝对不行的,因为之前我写过一种方法。。。随便填最后会到自己打自己。应该是按照升序来填,这样就会尽量避免和自己打。

【其它】
994465 02.02.10 15:31 edward 138 .CPP Accepted 25 ms 827 kb
【CODE】
#include #include #include #include using namespace std;
struct datat{int d,mark;}a[111];
int n,ans[111111][2];

bool cmp(datat x,datat y){return x.d>y.d;}

int main(){
int sum=0;
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i].d);
a[i].mark=i;
sum+=a[i].d;
}
sort(&a[1],&a[n+1],cmp);
sum/=2;
printf("%dn",sum);
int tot=0;
for (int i=1;i<=n;i++){
while (tota[i].d--;
tot++;
ans[tot][0]=a[i].mark;
}   
if (tottot++;
ans[tot][1]=a[i].mark;
ans[tot][0]=a[i+1].mark;
a[i+1].d--;
a[i].d--;
}   
}
int top=1;
while (a[top].d==0) top++;
for (int i=1;i<=sum;i++){
printf("%d ",ans[i][0]);
if (ans[i][1]) printf("%d",ans[i][1]);
else{
printf("%d",a[top].mark);
a[top].d--;
while (a[top].d==0) top++;
}  
printf("n");
}
}   

留下评论

您的电子邮箱地址不会被公开。