Question

pascal问题，就好像数学题一样的，就是不知道思路应该是怎样的，最好把思路和程序一起写一下！

问题是这样的：给定一堆正整数，要求你分成两堆，两堆数的和分别为S1和S2，谁分的方案使得S1*S1-S2*S2的结果小（规定S1>=S2），谁就将获得胜利。
注： S2可以等于0。
60%的数据， 1<=n<=20
80%的数据， 1<=n<=50， ai<=20
100%的数据， 1<=n<=100， ai<=100
样例输入
4
1 2 3 4
样例输出
0

Answer 1

把一堆n分成s1,s2 则s1+s2=n
s1*s1-s2*s2=(s1+s2)(s1-s2)=n(s1-s2)
可见两堆的数量的差越小越好，因此，若n=2m, 则取s1=s2=m; 若n=2m+1,则取s1=m+1, s2=m.这就是最优解。
照此思路编程即可，可能要用到随机数。

追问

可是这种方法我也想到了啊。但是如果他不是连续的自然数，例如：1 3 500 1，那又应该怎么取啊？

追答

是别人给您一堆，你把它分成两堆，不是别人给你4个数，根据分析两个相等或相邻是最好方案，不连续即相差很多不是好方案。

Answer 2

最简单的暴力枚举，把全部的方案都枚举一遍，找出差最小的，输出（数据大就会爆）

这是贪心（大约），从大到小排序，最大的是s1，第二大的是s2，都赋值为false，再一对一对做下去，尽量使差值的增加最小，赋值为false，若差值大于最小的不是false的数，就一路往上找最接近差值的数，加给s2。可能有漏洞，特殊情况

动规，不解释，枚举+最优+空间