P1281 [CERC1998] 书的复制

目录

题目描述

输入格式

输出格式

输入输出样例

说明/提示

题目思路

不会的看代码

---

题目描述

现在要把 m 本有顺序的书分给 k 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

输入格式

第一行两个整数 m,k。

第二行 m 个整数，第 i 个整数表示第 i 本书的页数。

输出格式

共 k 行，每行两个整数，第 i 行表示第 i 个人抄写的书的起始编号和终止编号。 k 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

输入输出样例

输入 #1

9 3
1 2 3 4 5 6 7 8 9

输出 #1

1 5
6 7
8 9

说明/提示

1≤k≤m≤500。

题目思路

用二分先枚举每个人的最少用去的时间，再去用数组读取输出。

不会的看代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,i,a[200010],sum,t,w,bao,mid,b[200010],c[200100],ma,xp[200010],yp[200010],x,s,p;
bool pd(int x){int p=1,s=0;for(i=n;i>=1;i--){//从大到小 if(s+a[i]<=x){s+=a[i];}//如果符合条件（也就是小于最小时间）就让s加上当前时间。 else if(a[i]<=x)s=a[i],p++; //特判如果a[i]比x大的情况，当然数据水，删去 也能过 }return p<=m;//判断需要的人数是否满足小于m的条件。 
}
main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>m;memset(a,0x3f,sizeof(a));for(i=1;i<=n;i++)cin>>a[i],sum+=a[i],ma=max(ma,a[i]);//sum，ma 来确定头尾 t=ma;w=sum; while(t<=w){//二分答案，答案是最小时间 mid=(t+w)>>1;if(pd(mid))w=mid-1,bao=mid;//bao来判断最优解 else t=mid+1;}p=1;x=bao;//p是第一个，bao是最优解。 for(i=n;i>=1;i--){if(s+a[i]<=x){s+=a[i];}else if(a[i]<=x)s=a[i],xp[p]=i+1,yp[++p]=i; //用数组来输出yp是上一个的末尾位置，xp是当前这个起始位置。 }xp[p]=1;yp[1]=n;//特判 for(i=m;i>=1;i--)cout<<xp[i]<<" "<<yp[i]<<"\n";//输出 
}