作者fgets (安全不会当)
看板C_and_CPP
标题[ACM ] 10032
时间Sun Aug 9 18:21:49 2009
题目大意：有n个人参加拔河比赛，分成2队，2队的人数最多只能相差1个人。
因为拔河的胜负通常与体重有很大的关系，所以我们希望2队总体重尽可能接近。
CODE:
http://nopaste.info/9f85348163.html
我的作法很简单，就是分成两队，
然後两队各取一人，如果交换可使两队重量差减少
则交换两人直到找不到可交换的为止。
但是不知道为什麽一直WA，想想解法应该没问题才对
不知道有没有人可以帮忙，感谢!
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int pa[100];
int pb[100];
void swap(int *a , int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main()
{
int t,i,j,n,T;
int a, b;
int ta,tb;
int sa,sb;
int ok,diff,found;
scanf("%d",&T);
for(t=0;t<T;t++)
{
if(t)
putchar('\n');
ok = sa = sb = 0;
scanf("%d",&n);
if(n % 2)
a = n/2 , b = n/2+1;
else
a = b = n/2;
for(i=0;i<a;i++)
{
scanf("%d",&pa[i]);
sa += pa[i];
}
for(i=0;i<b;i++)
{
scanf("%d",&pb[i]);
sb += pb[i];
}
diff = abs(sa - sb);
while(!ok)
{
found = 0;
for(i=0;i<a;i++)
for(j=0;j<b;j++)
{
ta = sa - pa[i] + pb[j];
tb = sb - pb[j] + pa[i];
if(diff > abs(ta - tb))
{
diff = abs(ta - tb);
sa = ta;
sb = tb;
swap(&pa[i],&pb[j]);
found = 1;
}
}
if(!found)
ok = 1;
}
if(sa < sb)
printf("%d %d\n",sa,sb);
else
printf("%d %d\n",sb,sa);
}
return 0;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.173.137.217
1F：→ pico2k:你确定你有看清楚题目的内容?... 08/09 20:45
2F：→ fgets:有，不然请问你觉得哪里有问题? 08/09 20:56
3F：推 electorn:greedy algorithm 绝对不行...之前我也跟你一样演算法 08/09 22:03
4F：→ electorn:後来找到极端 case... 交换不可行，除非再加上随机化 08/09 22:04
5F：→ pico2k:你处理input的方式跟题目差很多... 08/09 22:58
6F：推 ledia:有差很多吗 @@? 我看处理方式 ok 呀 08/09 23:55
7F：→ bleed1979:scanf("%d")可以滤掉'\n' 有没注意到空行没关系的 08/10 03:21
8F：推 Arton0306:没仔细看你的code 不过一开始分的时候两个人若应该是一 08/12 22:06
9F：→ Arton0306:队的 结果被你分成不同队 那怎麽换也换不成同一队 08/12 22:06
10F：→ Arton0306:看了一下code 确实会有这个问题 08/12 22:10
11F：→ Arton0306:咦 我错了XD 08/12 22:11
12F：推 Arton0306:那问题应该是出在有时可能一次要换2人以上 如 08/12 22:13
13F：→ Arton0306:10 0 <=> 5 5.5 只换一个会变不好 两个一起才会变好 08/12 22:14