题解 P1281 【书的复制】

· · 题解

我这是有几百年没写题解了（落泪

其实这是一道很有趣的题，对吧？其实挺有画面感的

那么，很多dalao都选择了使用动态规划，但本蒟蒻的做法是二分。

但看到没有一篇题解是很好的二分讲解啊，那么我来吧~

来先理解一下题意。

简而言之，就是：

把m个数分成k组，使每组数的和尽量平均。

那么，我们需要二分的其实是这个“平均”的值，也就是复制时间。

把二分出来的复制时间代到输入数据中，就可以判断这个复制时间是否可行。根据题目要求：

尽可能让前面的人少抄写

emmm这个怎么实现呢？

其实啊，我们这么想：我们面前有一面长长的桌子，桌子上从左到右整整齐齐摆着m本书，有k个可怜的娃要去抄书。要使前面的人少抄写，也就是抄靠右边的书的娃要多抄。那么，就要从抄靠右边的书的娃开始枚举，让他尽量多抄。


伪代码：

for m~1//给娃加书
{
    if 当前这个娃抄的书超过选择的复制时间 
        then 把这本书留下，换下一个娃来抄
        if 没有娃能来抄书了，就说明复制时间太短了
}

最后要特判：最后抄书最少的娃能不能抄完书，不能的话也是失败的！

于是，通过以上操作变可以二分出我们心心念念的复制时间了！！

然后，又是一个代入的过程，我们把得出的复制时间代入输入数据，再次从右到左枚举一次，就可以得出每个人抄书的范围。

但是，答案要从左往右输出，所以拿个数组记录下来就好惹！！

还有一些细节要注意，代码里都有注释了

完整代码：

/*
    m个数分成k组，使每组数的和尽量平均
*/

~written by 梦里调音~

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 505;
int m, k, a[N], ans;
int res[N][2];
bool lovemok(int p)
{
    int now = k;//还剩多少人能抄书(包括正在抄书的人)
    int cnt = 0;//这个人要抄书的页数
    for (int i = m; i > 0; i--)
    {
        cnt += a[i];
        if (cnt > p)
        {
            cnt = a[i], now--;
        }

        if (now <= 0)return false;//书还没抄完，但已经没有人可以去抄书了
    }
    if(cnt > p)return false;
    return true;
}
void print()
{
    int id = k, cnt = 0, st = m;//这个人的编号，当前这个人已经抄的页数，这个人开始抄书的起点
    for (int i = m; i > 0; i--)
    {
        cnt += a[i];
        if (cnt > ans)
        {
            cnt = a[i];
            res[id][0] = i + 1;
            res[id][1] = st;
            st = i;
            --id;
        }
    }
    //最后一个人的特殊处理
    res[1][0] = 1;
    res[1][1] = st;

    //输出
    for (int i = 1; i <= k; i++)
        cout << res[i][0] << " " << res[i][1] << endl;
    return;
}
signed main()
{
    int l = 0, r = 0, mid;
    scanf("%d%d", &m, &k);
    if (!m) {//特判注意一下
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= m; i++)
        scanf("%d", &a[i]), r += a[i];
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (lovemok(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    print();
    return 0;
}