Question

pascal 竞赛试题求解！

小李对故乡的思念全部化作了对雾霾天气的怨念，这引起了掌控雾霾的邪神的极大不满，邪神派去了
一只小怪兽去对付小李，由于这只怪兽拥有极高的IQ，它觉得直接消灭小李太没有难度了，它决定要和小
李在智力水平上一较高下。我们可否帮助小李来战胜强大的怪兽呢？问题是这样的：给定一堆正整数，要求你分成两堆，两堆数的和分别为S1和S2，谁分的方案使得S1*S1-S2*S2的结果小（规定S1>=S2），谁就将获得胜利。
注：
S2可以等于0。
【输入】
第一行n，表示共有n个数
第二行共n个用空格隔开的正整数ai，表示给定的一堆正整数。
【输出】
输出就一个整数，表示S1*S1-S2*S2的最小值。
【样例输入】
4
1 2 3 4
【样例输出】
0
【样例说明】
1和4一堆，2和3一堆，5*5-5*5 = 0
【数据规模】
60%的数据，1<=n<=20
80%的数据，1<=n<=50，ai<=20
100%的数据，1<=n<=100，ai<=100

Answer 1

有平方差公式s1*s1-s2*s2=(s1+s2)*(s1-s2)。

显然s1+s2的值是固定的，所以只需使(s1-s2)的值最小。

通过计算可以得出由a中的几个数字可以组成的和(f[i]值为true表示存在方案组成i)

为使s1-s2值最小，只需使s2最接近平均数即可

program wapiknow;
var n,i,j,s1,s2,sum:longint;
    a:array[1..100] of longint;
    f:array[0..11000] of boolean;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  fillchar(f,sizeof(f),false);
  f[0]:=true;
  for i:=1 to n do
    for j:=10000 downto 0 do
      if (f[j]=true) then f[j+a[i]]:=true;
  sum:=0;
  for i:=1 to n do sum:=sum+a[i];
  for i:=sum div 2 downto 0 do
    if (f[i]=true) then
    begin
      s2:=i;
      break;
    end;
  s1:=sum-s2;
  writeln(s1*s1-s2*s2);
end.

希望我的回答能帮到你。

Answer 2

这个就是让你把一堆数分成两份最为接近的，再求平方差