复制书稿

发布时间: 2017年6月19日 00:27   时间限制: 1000ms   内存限制: 128M

假设有m本书(编号为12m),想将每本复制一份,m本书的页数可能不同(分别是P1P2…Pm)。任务是将这m本书分给k个抄写员(k=m〉,每本书只能分配给一个抄写员进行复制,而每个抄写员所分配到的书必须是连续顺序的。意思是说,存在一个连续升序数列 0 = b[0] < b[1] < b[2] < … < b[k-1] < b[k] = m,这样,第i号抄写员得到的书稿是从b[i-1]+1到第bi本书。复制工作是同时开始进行的,并且每个抄写员复制的速度都是一样的。所以,复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案,使分配给这k个抄写员抄写这m本书时,完成所有抄写任务的时间最小。 

输入由若干个测试数据组成。每组测试数据有两行,第一行两个数是mk:表示书本数目与抄写人数;第二行是m个由空格分隔的整数,表示m本书中每本的页数。(1km500),这m个整数均为正整数且都不超过1 000 000

对第i组测试数据,输出一行。先输出“Case i:”,接着输出这k个抄写员抄写这m本书时,完成所有抄写任务的最小时间。

复制
9 3
1 2 3 4 5 6 7 8 9
Case 1: 17
1992

old_judge

old_judge_None