P1281 书的复制
网页链接
P1281 书的复制
题目背景
大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出0 0。
不过，已经修改数据，保证每个人都有活可干。
题目描述
现在要把m mm本有顺序的书分给k kk个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
输入格式
第一行两个整数m , k m,km,k。
第二行m mm个整数，第i ii个整数表示第i ii本书的页数。
输出格式
共k kk行，每行两个整数，第i ii行表示第i ii个人抄写的书的起始编号和终止编号。k kk行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
输入输出样例 #1
输入 #1
9 3 1 2 3 4 5 6 7 8 9输出 #1
1 5 6 7 8 9说明/提示
1 ≤ k ≤ m ≤ 500 1\le k \le m \le 5001≤k≤m≤500，所有书的页数都是正整数且不超过10 4 10^4104。
解题思路
本题是经典的二分答案+贪心分配问题，核心求解最短抄写时间并输出分配方案。采用二分查找确定最小复制时间：左边界为单本书的最大页数，右边界为所有书的总页数。通过check函数从后往前贪心分配书籍，统计完成抄写所需的最少人数，若人数不超过规定人数则当前时间可行。找到最短时间后，再次从后往前划分书籍，确保前面的人抄写数量最少（满足题目多解要求），最后将划分结果反转，按顺序输出每个人的抄写区间。算法时间复杂度低，完美适配题目数据范围。
总结
核心逻辑：二分答案求解最小最大抄写时间，反向贪心分配书籍满足「前面的人少抄写」的规则。
关键操作：二分边界初始化、反向贪心校验人数、反向划分区间后反转输出。
效率保障：二分配合贪心策略，计算简洁高效，严格符合题目输出要求。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m;ll a[505];ll x[505],y[505];boolcheck(ll s){ll num=1,t=0;for(ll i=n;i>=1;i--){if(t+a[i]>s)t=0,num++;t+=a[i];}returnnum<=m;}llfind(ll low,ll high){ll mid;while(low+1<high){mid=low+(high-low)/2;if(check(mid))high=mid;elselow=mid;}returnhigh;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll low=0,high=0;cin>>n>>m;for(ll i=1;i<=n;i++){cin>>a[i];high+=a[i];low=max(low,a[i]);}ll s=find(low,high);ll t=0,num=1;for(ll i=1;i<=m;i++)x[i]=y[i]=0;y[1]=n;for(ll i=n;i>=1;i--){if(t+a[i]>s){t=0;x[num]=i+1;y[++num]=i;}t+=a[i];}x[num]=1;for(ll i=m;i>=1;i--)cout<<x[i]<<" "<<y[i]<<endl;return0;}
