九度:/problem.php?pid=1502题目描述:
在印刷术发明之前,复制一本书是一个很困难的工作,工作量很大,而且需要大家的积极配合来抄写一本书,团队合作能力很重要。
当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书,编号为1,2,3...m, 每本书有1<=x<=100000页, 把这些书分配给k个抄写员,要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的,你的任务就是找到一个最佳的分配方案,使得所有书被抄完所用的时间最少。
输入:
输入可能包含多个测试样例。
第一行仅包含正整数 n,表示测试案例的个数。
对于每个测试案例,每个案例由两行组成,在第一行中,有两个整数m和 k, 1<=k<=m<=500。 在第二行中,有m个整数用空格分隔。 所有这些值都为正且小于100000。
输出:
对应每个测试案例,
输出一行数字,代表最佳的分配方案全部抄写完毕所需要的时间。
样例输入:
29 3100 200 300 400 500 600 700 800 9005 4100 100 100 100 100
样例输出:
1700200
这个题目的解法比较有趣。我们先定义一个人抄的页数的总和为工作量。
首先,一个合理的答案ans应该满足下面的条件:
1、 每一份工作量不大于ans,且其中一份或者几份的工作量等于ans。
2、 分成的份数不大于k。
但是满足上述条件的ans未必是最优解。例如ans=所有页数的总和时,也一样满足上述两个条件。仔细想想,我们的目的是使得书籍正好可以被所有人抄完,且尽量不要有人闲着,换言之,我们应该找出来一个值t,它应该满足第三个条件:t如果被减1,条件1或者2会被破坏。可以用反证法证明,t是最优解。
由于这个题目有个特殊性,就是每个人只能抄连续的几本书,故我们可以二分得到答案。取所有书籍页数最多的为下界base,所有书籍的页数和为上界top,每次验证mid是否满足条件1和2,满足则top=mid-1,否则base=mid+1。最后base就是我们所需要的答案。
有人会问为什么去页数最多不是最少?最少当然也可以,但是别忘了条件1,每份工作量不大于ans,因此最小没有意义。而且甚至如果二分时判断每份工作量不大于ans的代码有问题,反而还可能会导致错误。
时间复杂度是O(NlogM),其中M为所有数字之和,N为书的数目
#include <stdio.h>long long book[502];bool check(long long mid, int m, int k){int cnt = 0;long long sum = 0;for(int i = 1; i <= m; i ++){if(sum + book[i ] > mid){cnt ++;sum = book[i ];}elsesum += book[i ];}cnt ++;if(cnt <= k) return true;else return false;}int main(){int N;scanf("%d", &N);while(N--){int m, k;scanf("%d%d", &m, &k);long long top = 0;long long base = 0;for(int i = 1; i <= m; i ++){scanf("%lld", &book[i ]);top += book[i ];if(book[i ] > base)base = book[i ];}while(top >= base){long long mid = (top + base) / 2;if(check(mid, m, k))top = mid - 1;elsebase = mid + 1;}printf("%d\n", base);}return 0;}