| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1274
K_Star风波
Time Limit: 1000ms
Memory Limit: 65536kb Description
USTC的K_Star已成为USTC的标志性文化之一了，每年都会吸引很多俊男俏女前来参赛，当然今年也不例外。现在假设共有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
输出包括M+1行，第一行为评委们最短的点评时间。第i(2<=i<=M+1)行分别为第i-1位评委要点评歌手的起始编号和终止编号。如果有多组解，尽可能让前面的评委少点评。
Sample Input
1 5 3 4 5 3 1 2 Sample Output
6 1 1 2 2 3 5 |