[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).