题目链接

首先，通关观察题意，发现是让我们选择分类。

那么我们一开始需要得到最少的时间这个变量。所以我们可以二分答案查找这个最少的时间。找到这个最少的时间之后再去枚举这个过程。当然这道题中，尽量让前面的人少抄写。也就是让后面的人多抄写，那就从后往前，尽可能的多拿，剩下的就是前面需要拿的。

Code:

// Problem: 书的复制

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 501;

int a[MAXN + 1];

int n, m;

bool check(int x)
{
    int cnt = 0, k = 1;
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] > x)
        {
            return false;
        }
        if (cnt + a[i] > x)
        {
            k ++;
            cnt = a[i];
        }
        else
        {
            cnt += a[i];
        }
    }
    return k <= m;
}

pair<int, int> res[10001];

void getans(int x)
{
    int k = m, f = 0;
    res[k].first = n;
    for (int i = n; i >= 1; i -- )
    {
        f += a[i];
        if (f > x)
        {
            f = a[i];
            res[k].second = i + 1;
            k --;
            res[k].first = i;
        }
    }
    res[1].second = 1;
    for (int i = 1; i <= m; i ++ )
    {
        printf("%d %d\n", res[i].second, res[i].first);
    }
}

int main()
{
    int l, r;
    scanf("%d%d", &n, &m);
    l = 1;
    r = 100001;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    while(r - l > 5)
    {
        int mid = (r + l) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    int res = 0;
    for (int i = l; i <= r; i ++ )
    {
        if (check(i))
        {
            res = i;
            break;
        }
    }
    getans(res);
    return 0;
}

最后立个Flag, 这几天写一下二分答案的博客。

• [ ] 是否填坑