洛谷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;
}