Chinaunix

标题: 数组划分问题 [打印本页]

作者: isohybrid 时间: 2013-03-21 17:51
标题: 数组划分问题
Problem Description
现在假设共有N名歌手和M名评委，歌手编号为1,2…,N，评委编号为1,2..M。歌手歌唱的时间分别为T1,T2,..,TN。评委们需要对歌手进行点评，且每名歌手需要且仅需要一名评委进行点评，每名评委至少要对一名歌手进行点评，且每一位评委只能对连续编号的某些歌手进行点评，点评时间为这些歌手唱歌时间之和。
现在请你来设计一种点评方案，使得评委们的点评时间尽可能的短。评委们的点评时间定义为点评时间最多的那位评委所用掉的时间。
举个例子：假设有5个歌手，3个评委。歌手的歌唱时间依次为：4 5 3 1 2，那么可以这样进行点评： 4 /5 3 1/ 2 ,即第一位评委点评第一位歌手，用时4个单位；第二位评委点评第二，三，四位歌手，用时9个单位；第三位评委点评第五位歌手，用时2个单位；那么该方案的点评时间为9。
当然这并不是最优的方案，最优方案需要你用程序找出。
Input
第一行一个整数T(T<=100)，代表共有T组测试数据。
每组测试数据包括两部分：
第一部分：N M 分别代表歌手数和评委数。(1<=M<=N<=500)
第二部分：N个正整数，分别代表歌手的歌唱时间(不大于2000的正整数)。
Output
输出包括T行，每一行为每个测试用例评委们最短的点评时间。
Sample Input
1
5 3
4 5 3 1 2
Sample Output
6
Author
gamegame151

作者: daybreakcx 时间: 2013-03-22 09:20
二分点评最短时间，然后每次贪心判断是否可行

作者: firefox_hy 时间: 2013-03-22 10:17
同楼上，二分最短时间然后贪心尽可能让更多的歌手放在一组里
你需要思考为什么能二分（满足单调性）和贪心（满足贪心算法理论）。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)