Summary

洛谷 P1281 书的复制 的题解,
算法为 二分 .

Link

题目链接

Text

一本书不允许给两个 (或以上) 的人抄写, 分给每一个人的书, 必须是连续的, 比如不能把第一, 第三, 第四本书给同一个人抄写.

显然这道题具有典型区间 DP 的特征, 状态很容易想出来: 用 f[i][j]表示已经分配了 i 份书稿, 分配给了 j 个人. 然而我不想去想状态转移方程, 再一看

使得复制时间最短

求最小值当然也可以用二分啊!

于是就是对细节的处理:

• 二分时要注意上下界, 防止舍去了正确答案. 谨防在减小上界时舍去当前 mid, 因为可能当前 mid 即是最短时间;
• 要求前面的人尽量少抄, 所以检验答案可以顺向搜索, 但输出时要反向输出.

由上写出代码:

#include <cstdio>
using namespace std;

int m, k, s[505], lft, rgt = 300000, mid, now, cnt, f[505], t[505];

int main()
{
    scanf("%d%d", &m, &k);
    for (int i = 0; i < m; i++)
        scanf("%d", &s[i]);
    while (lft < rgt)
    {
        mid = (lft + rgt) >> 1;
        now = 0, cnt = 1;
        for (int i = 0; i < m; i++)
        {
            if (now + s[i] <= mid)
                now += s[i];
            else
                now = s[i], cnt++;
        }
        if (cnt > k)
            lft = mid + 1;
        else
            rgt = mid;
    }
    now = 0, cnt = k - 1, f[0] = 1, t[k - 1] = m;
    for (int i = m - 1; i >= 0; i--)
    {
        if (now + s[i] <= rgt)
            now += s[i];
        else
            f[cnt--] = i + 2, t[cnt] = i + 1, now = s[i];
    }
    for (int i = 0; i < k; i++)
        printf("%d %d\n", f[i], t[i]);
    return 0;
}

, 然而当你交上去这份代码, 你会发现 只有 90 分 . 下载测试数据来看, 这个数据点最后一本书页数远大于前面所有书的总和. 发现是自己对最后一本书能否抄完的判断不完善, 故想出解决办法:

再加一本书

具体操作是将

for (int i = 0; i < m; i++)

改为

for (int i = 0; i <= m; i++)

这样就多出了一本页数为 0 的书 s[m], 避开了对数据中最后一本书的处理.

Code

#include <cstdio>
using namespace std;

int m, k, s[505], lft, rgt = 300000, mid, now, cnt, f[505], t[505];

int main()
{
    scanf("%d%d", &m, &k);
    for (int i = 0; i < m; i++)
        scanf("%d", &s[i]);
    while (lft < rgt)
    {
        mid = (lft + rgt) >> 1;
        now = 0, cnt = 1;
        for (int i = 0; i <= m; i++)
        {
            if (now + s[i] <= mid)
                now += s[i];
            else
                now = s[i], cnt++;
        }
        if (cnt > k)
            lft = mid + 1;
        else
            rgt = mid;
    }
    now = 0, cnt = k - 1, f[0] = 1, t[k - 1] = m;
    for (int i = m - 1; i >= 0; i--)
    {
        if (now + s[i] <= rgt)
            now += s[i];
        else
            f[cnt--] = i + 2, t[cnt] = i + 1, now = s[i];
    }
    for (int i = 0; i < k; i++)
        printf("%d %d\n", f[i], t[i]);
    return 0;
}