二分 + 贪心

1.二分思路

要将m本书顺序分成k个部分给k个人去抄，要使得抄书时间最短（大家同时开始抄，使得需要最长时间的那个人用时最短）。则我们只需要找到一个时间 time，能将m本书刚好划分为k个段给k个人抄写即可。那么如何找这个time呢？使用二分法找即可。

2.如何确定二分边界？

l = max(w[i])：因为一本书只能给一个人抄，因此 l 最小取所有书中的最大页数；
r = 1e9：题目未给定最大值，如果该值不满足条件，可以改成更大的值。

3.注意（贪心思路）

因为题目要求让前面的人尽可能少抄，因此求划分方案时应该从后往前枚举，即让后边的人尽可能多抄，就可以让前面的人少抄。

#include<iostream>
using namespace std;

const int N = 510;
int w[N], L[N], R[N]; //L 和 R 记录每一段的左右区间
int m, k;

bool check(int sum)
{
    int s = 0, cnt = 1; //cnt表示被划分的段数
    R[cnt] = m; //该段的右区间

    //题目要求让前面的人尽可能少抄，那么就从序列后面往前面遍历，让后面的人尽可能多抄
    for(int i=m; i; i--)
    {
        //
        if(s + w[i] <= sum) s += w[i];
        else
        {
            L[cnt] = i+1; //该段的左区间
            cnt ++;
            R[cnt] = i; //下一段的右区间
            s = w[i]; //下一段重新开始累加
        }
    }
    L[cnt] = 1;
    return cnt <= k; //sum太大，导致被划分的段数少于等于k段
}

int main()
{
    cin>>m>>k;
    int l = 0, r = 1e9;
    //读入m本书
    for(int i=1; i<=m; i++)
    {
        cin>>w[i];
        l = max(l, w[i]);
    } 

    while(l < r)
    {
        int mid = l + r >>1;
        if(check(mid))  r = mid;
        else l = mid +1;
    }

    //此时l=r，check(r)以求出各段区间
    check(r);
    //cout<<r<<endl;
    for(int i=k; i; i--) cout<<L[i]<<' '<<R[i]<<endl;
    return 0;
}