木叶的军师

（nara..pas./c./cpp）

时间限制：5s，空间限制：256MB

题目背景：

奈良鹿丸，拥有出众的应敌策略，头脑冷静、随机应变，IQ超过200。在第四次忍界大战时，父亲奈良鹿久死亡，鹿丸成为木叶乃至忍者联军的新任军师。最后成为了鸣人的左右手，与沙暴手鞠成婚……

题目描述：

既然是军师，鹿丸就必须要为木叶村的忍者编队。可是，他最怕麻烦了。所以它将这个任务交给了你。木叶村有T个中队，你需要将每个中队的n名忍者分为m个组。每个忍者都有一个能力值ai，每组人数不一定要相等，但每个忍者都要且只能被分在其中一个组中。每个组因为组员能力的差异，所以有一个“不默契值”，该值为本组的（maxa-mina）^2，请你帮鹿丸找出最优的分组方案，使a中队所有组的“不默契值”总和最小。

输入描述：

第一行一个整数T，表示有T个中队。

接下来T*2行，每两行表示一个中队。其中第一行为两个整数n,m，表示该中队的忍者数和要分的组数；第二行为n个数字依次表示这个中队每个忍者的能力值ai。

输出描述：

对于第i个中队，输出“Team i: x”,其中x为最小的“不默契值”总和。

样例输入：

2

5 2

1 3 4 8 2

3 1

1 2 3

样例输出：

Team 1: 9

Team 2: 4

数据范围：

20%的数据保证T<=4，n<=1000，m<=100。

100%的数据保证T<=7,n<=10000，m<=5000,保证所有运算不超过32位整数。数据保证是随机的。

题解

二维斜率优化裸题