2014年第29宁波市小学生程序设计竞赛试题

宁波市第 29 届中小学生计算机程序设计竞赛复赛试题（小学组）第 5 页 共 6 页

3. 小李发奖金

(money.cpp/pas/c)

【题目描述】

当然打台球只是小李的休闲娱乐活动，对待他的本职工作，他还是非常兢兢业业的。但是小李的老板是个周扒皮，每次都想克扣小李的工资和奖金，甚至制定出非常奇葩的规则。

又到了每年发年终奖的时候了，今年老板的规则是这样的：给你n个数，每次你可以对任意一个数加1，直到所有的数都不相等为止，每加一次都要花费一定数额的费用。为了小李的幸福生活，聪明的你可否帮助小李，让他尽量少扣钱。

【输入】

第一行n，表示共有n个数。

第二行共n个用空格隔开的非负整数ai。

【输出】

仅一个整数，表示加到让每个数都不相等的最少次数。

【样例输入】

4 1 1 3 2

【样例输出】

3

【样例说明】

让1+1+1+1 = 4，给定的数字变成4,1,3,2。

【数据规模】

30%的数据，1<=n<=10 60%的数据，1<=n<=1000

80%的数据，1<=n<=30000，ai<=1000， 100%的数据，1<=n<=30000， ai<=1000000。

宁波市第 29 届中小学生计算机程序设计竞赛复赛试题（小学组）第 6 页 共 6 页

4. 小李打怪兽

(monster.cpp/pas/c)

【题目描述】

小李对故乡的思念全部化作了对雾霾天气的怨念，这引起了掌控雾霾的邪神的极大不满，邪神派去了一只小怪兽去对付小李，由于这只怪兽拥有极高的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