[ACM ] 10032

[fgets (安全不會當)]

題目大意：有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
→ pico2k:你確定你有看清楚題目的內容?...
→ fgets:有，不然請問你覺得哪裡有問題?
推 electorn:greedy algorithm 絕對不行...之前我也跟你一樣演算法
→ electorn:後來找到極端 case... 交換不可行，除非再加上隨機化
→ pico2k:你處理input的方式跟題目差很多...
推 ledia:有差很多嗎 @@? 我看處理方式 ok 呀
→ bleed1979:scanf("%d")可以濾掉'\n'　有沒注意到空行沒關係的
推 Arton0306:沒仔細看你的code 不過一開始分的時候兩個人若應該是一
→ Arton0306:隊的 結果被你分成不同隊 那怎麼換也換不成同一隊
→ Arton0306:看了一下code 確實會有這個問題
→ Arton0306:咦 我錯了XD
推 Arton0306:那問題應該是出在有時可能一次要換2人以上 如
→ Arton0306:10 0 <=> 5 5.5 只換一個會變不好 兩個一起才會變好