问题描述
【描述 Description】
新一年度的猫狗大战通过SC(星际争霸)这款经典的游戏来较量，野猫和飞狗这对冤家为此已经准备好久了，为了使战争更有难度和戏剧性，双方约定只能选择Terran(人族)并且只能造机枪兵。
比赛开始了，很快，野猫已经攒足几队机枪兵，试探性的发动进攻；然而，飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了，于是，便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口，飞狗的兵补给会很快，野猫看敌不过，决定撤退。这时飞狗的兵力也不足够多，所以没追出来。
由于不允许造医生，机枪兵没办法补血。受伤的兵只好忍了。555－
现在，野猫又攒足了足够的兵力，决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击，野猫决定把现有的兵分成两部分，从两路进攻。由于有些兵在第一次战斗中受伤了，为了使两部分的兵实力平均些，分的规则是这样的：1）两部分兵的个数最多只能差一个；2）每部分兵的血值总和必须要尽可能接近。现在请你编写一个程序，给定野猫现在有的兵的个数以及每个兵的血格值，求出野猫按上述规则分成两部分后每部分兵的血值总和。
【输入格式 Input Format】
第一行为一个整数n(1<=n<=200)，表示野猫现在有的机枪兵的个数。以下的n行每行一个整数，表示每个机枪兵的血格(1<=ai<=40)。
【输出格式 Output Format 】
只有一行，包含两个数，即野猫的每部分兵的血值总和，较小的一个值放在前面，两个数用空格分隔。
【样例输入 Sample Input 】
3
35
20
32
【样例输出 Sample Output】
35 52
【算法分析】
1 to n div 2为前一半数，n div 2+1 to n为后一半数之后枚举a[i],a[j]看是否可以交换
代码
方法一：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <stdio.h> int abs(int t) { if (t < 0) return -t; else return t; } int main() { int a[201], b[201]; int n, i, j, l1, l2, sum1 , sum2, temp; scanf("%d", &n); l1 = n / 2; l2 = n - l1; sum1 = 0; sum2 = 0; for (i = 1; i <= l1; i++) { scanf("%d", &a[i]); sum1 += a[i]; } for (i = 1; i <= l2; i++) { scanf("%d", &b[i]); sum2 += b[i]; } for (i = 1; i <= l1; i++) { for (j = 1; j <= l2; j++) { if (abs((sum1 + b[j] - a[i]) - (sum2 + a[i] - b[j])) < abs(sum1 - sum2)) { sum1 = sum1 + b[j] - a[i]; sum2 = sum2 + a[i] - b[j]; temp = a[i]; a[i] = b[j]; b[j] = temp; } } } if (sum1 < sum2) printf("%d %d\n", sum1, sum2); else printf("%d %d\n", sum2, sum1); return 0; } |
方法二：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | Const maxn=200; maxm=8000; Var f:array[0..maxn,0..maxm] of boolean; n,ans,mid:integer; d:array[1..maxn] of integer; Procedure Init; var i:integer; begin fillchar(f,sizeof(f),false); f[0,0]:=true; ans:=0; readln(n); for i:=1 to n do readln(d[i]); for i:=1 to n do ans:=ans+d[i]; mid:=ans div 2; end; Procedure Work; var i,j,k:integer; begin for i:=1 to n do for k:=i downto 1 do for j:=mid-d[i] downto 0 do if f[k-1,j] then f[k,j+d[i]]:=true; end; Procedure Print; var i,j:integer; begin i:=0;j:=0; while (not f[n div 2,mid+j]) do dec(j); j:=mid+j; writeln(j,' ',ans-j); end; BEGIN init; work; print; END. |