[ACM ] 10032
題目大意：有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
→
08/09 20:45, , 1F
08/09 20:45, 1F
→
08/09 20:56, , 2F
08/09 20:56, 2F
推
08/09 22:03, , 3F
08/09 22:03, 3F
→
08/09 22:04, , 4F
08/09 22:04, 4F
→
08/09 22:58, , 5F
08/09 22:58, 5F
推
08/09 23:55, , 6F
08/09 23:55, 6F
→
08/10 03:21, , 7F
08/10 03:21, 7F
推
08/12 22:06, , 8F
08/12 22:06, 8F
→
08/12 22:06, , 9F
08/12 22:06, 9F
→
08/12 22:10, , 10F
08/12 22:10, 10F
→
08/12 22:11, , 11F
08/12 22:11, 11F
推
08/12 22:13, , 12F
08/12 22:13, 12F
→
08/12 22:14, , 13F
08/12 22:14, 13F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
