洛谷P1281 书的复制
url: https://www.luogu.com.cn/problem/P1281
tag：
二分，贪心
思路：
求可以满足条件的最小值，所以可以想到用二分来做。二分的是复制时间，所以范围是在0到全部的页数。二分的思路是利用这个复制时间来求出一个需要的人数，将这个人数和题目所给的认识做一个比较，因为要满足条件，所以人数需要小于等于题目给的人数。可以知道如果复制时间越大，表示一个人可以抄的书越多，需要的人数越少，所以人数和复制时间是单调递减的关系。利用这个单调递减的关系，可以二分出一个复制时间，使得这个复制时间是当所需人数小于等于所需人数时，复制时间最小。然后就可以通过这个复制时间来求出每一个人所抄的书的起始范围。因为要求是让前面的人尽可能的少抄，所以就需要让后面的人多抄，因此再输出答案的时候用到了贪心的思想，从后往前遍历书，使得每次每个人都尽可能抄多一点的书，通过这种遍历方式实现题目要求的让前面的人尽可能少抄。在二分的时候也有用到这种遍历方式，但是后面写题解的时候觉得或许二分的时候不需要，因为只是求一个人数，没有前后之分。
代码：
#include <iostream>
using namespace std;
int m, k;
const int N = 550;
int a[N];
int x[N], y[N];
bool check(int x)
{
int now = 1;
int cnt = 0;
for (int i = m - 1; i >= 0; i --)
{
if (cnt + a[i] > x)
{
cnt = 0;
now ++;
}
cnt += a[i];
}
return now <= k;
}
int main()
{
cin >> m >> k;
int kk = k;
int l = 0, r = 0;
for (int i = 0; i < m; i ++)
{
cin >> a[i];
r += a[i];
}
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
int t = 0;
y[k] = m; x[1] = 1;
for (int i = m - 1; i >= 0; i --)
{
if (t + a[i] > l)
{
t = 0;
x[k] = i + 2;
y[--k] = i + 1;
}
t += a[i];
}
for (int i = 1; i <= kk; i ++)
{
cout << x[i] << ' ' << y[i] << '\n';
}
return 0;
}