今天突然意识到复制书稿这道题目应该是可以用贪心法来做的，几经周折无法证明贪心法的正确性。等改日强大了再来证明。也欢迎高手提供答案。
解法如下，先将M本书分为M组，然后尝试选择连续的两个组合并，要求选择的这两个组合并后的值是所有可能的连续两两合并的值最小的，例如，1,2,3三组， 12合并和23合并显然12合并最小，采取该种合并方式。
如此迭代至K组时即可。
通常思路如下：
证明：（每一步所做的贪心选择最终导致问题的整体最优解）
//基本思路：考察一个问题的最优解，证明可修改该最优解，使得其从贪心选择开始，然后用数学归纳法证明每一步都可以通过贪心选择得到最优解
1，假定首选元素不是贪心选择所要的元素，证明将首元素替换成贪心选择所需元素，依然得到最优解；
2，数学归纳法证明每一步均可通过贪心选择得到最优解
假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P
1，P2，…PM）。任务是将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写
员进行复制，而每个抄写员所分配到的书必须是连续顺序的。
意思是说，存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m，这样，第
I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的，并且每个抄写
员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那
个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽
可能小（如存在多个最优方案，只输出其中一种）。
(GDOI\'\'99 Books).
〖输入格式〗
第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.
〖输出格式〗
共k行。每行两个整数：第I行表示第I抄写员抄的书本编号起止。
〖输入输出样例〗
输入样例
9 3
1 2 3 4 5 6 7 8 9
输出样例
1 5
6 7
8 9
阅读(2031) | 评论(0) | 转发(1) |
