【火影完结纪念赛】木叶的军师

2015年1月18日1,6420

木叶的军师

(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位整数。数据保证是随机的。

题解

二维斜率优化裸题