猫狗大战

问题描述
【描述 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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注


*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>