「CodeVS 3168 / 3162」抄书问题 - 划分 DP / 二分答案

发表于 | 分类于

把 M 本有顺序的书分给 K 个人抄写，每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的（比如不能把第一、第三、第四本数给同一个人抄写）。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

链接

CodeVS 3162 - 抄书问题
CodeVS 3168 - 抄书问题 3

划分 DP

考虑用动态规划求出最短时间，以 表示第 m 本书的页数， 表示前 m 本书给前 k 个人抄需要的最短时间。

边界条件为：

转移方程为：

即，枚举第 k 个人抄的书数，从“前面 k - 1 个人每人只抄一本，剩下的全留给第 k 个人”到“前面 k - 1 个人一共抄 m - 1 本，给第 k 个人留一本”，并上第 k 个人抄的时间，取最小值。

求书本页数的区间和可以用一个前缀和数组来优化时间复杂度，故该算法时间复杂度为 。

int search(int m, int k) {
    if (f[m - 1][k - 1] == -1) {

        if (k == 1) {
            f[m - 1][k - 1] = sum(0, m - 1);
        } else {
            for (int i = k - 1; i <= m - 1; i++) {
                int ans = std::max(search(i, k - 1), sum(i + 1 - 1, m - 1));
                if (f[m - 1][k - 1] == -1 || f[m - 1][k - 1] > ans) {
                    f[m - 1][k - 1] = ans;
                }
            }
        }
    }

    return f[m - 1][k - 1];
}

二分答案

加大后的数据量已不能使用 DP 的方法，考虑对最短时间在最大页数到总页数之间进行二分，检验过程贪心枚举每一本书，从最后一个人开始，如果当前的人还能抄就给他抄，否则给前一个人抄，如果最后能抄完则可行。

时间复杂度为 。

inline bool check(int limit) {
    memset(pageCount, 0, sizeof(pageCount));

    int j = k - 1, lastEnd = m - 1;
    for (int i = m - 1; i >= 0; i--) {
        if (pageCount[j] + a[i] <= limit) {
            pageCount[j] += a[i];
        } else {
            if (j == 0) {
                return false;
            }

            lastEnd = i;
            pageCount[--j] += a[i];
        }
    }

    return sum(0, lastEnd - 1) <= limit;
}

inline int binaryDivide() {
    int l = max, r = sum(0, m - 1);
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    return l;
}

方案输出

输出方案算是这题最难的地方。~才不会告诉你们我 WA 了 8 次呢！~

和二分答案求最短时间的思路相似，贪心枚举每本书，从最后一个人开始（注意题目要求前面的人少抄），如果当前人还能抄，就给他抄，否则给下一个人抄，如果剩余人的数量大于剩余书的数量，则无论如何都要给下一个人抄（后面的全给抄完了咱前面的吵啥啊）。

输出顺序可以用一个栈来调整。

inline void printPlan() {
    memset(pageCount, 0, sizeof(pageCount));

    int j = k - 1, lastEnd = m - 1;
    stack<pair<int, int> > s;
    for (int i = m - 1; i >= 0; i--) {
        if (j > i || pageCount[j] + a[i] > ans) {
            pageCount[--j] += a[i];
            s.push(make_pair(i + 1 + 1, lastEnd + 1));
            lastEnd = i;
        } else {
            pageCount[j] += a[i];
        }
    }

    printf("%d %d\n", 1, lastEnd + 1);
    while (!s.empty()) {
        pair<int, int> range = s.top();
        s.pop();
        printf("%d %d\n", range.first, range.second);
    }
}

代码（划分 DP，CodeVS 3162）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <utility>

using std::stack;
using std::pair;
using std::make_pair;

const int MAXM = 100;
const int MAXK = 100;

int m, k;
int a[MAXM], prefix[MAXM], f[MAXM][MAXK], pageCount[MAXK];
int ans;

inline void makePrefix() {
    prefix[0] = a[0];
    for (int i = 1; i < m; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
}

inline int sum(int i, int j) {
    return i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
}

int search(int m, int k) {
    if (f[m - 1][k - 1] == -1) {

        if (k == 1) {
            f[m - 1][k - 1] = sum(0, m - 1);
        } else {
            for (int i = k - 1; i <= m - 1; i++) {
                int ans = std::max(search(i, k - 1), sum(i + 1 - 1, m - 1));
                if (f[m - 1][k - 1] == -1 || f[m - 1][k - 1] > ans) {
                    f[m - 1][k - 1] = ans;
                }
            }
        }
    }

    return f[m - 1][k - 1];
}

inline void printPlan() {
    memset(pageCount, 0, sizeof(pageCount));

    int j = k - 1, lastEnd = m - 1;
    stack<pair<int, int> > s;
    for (int i = m - 1; i >= 0; i--) {
        if (j > i || pageCount[j] + a[i] > ans) {
            pageCount[--j] += a[i];
            s.push(make_pair(i + 1 + 1, lastEnd + 1));
            lastEnd = i;
        } else {
            pageCount[j] += a[i];
        }
    }

    printf("%d %d\n", 1, lastEnd + 1);
    while (!s.empty()) {
        pair<int, int> range = s.top();
        s.pop();
        printf("%d %d\n", range.first, range.second);
    }
}

int main() {
    scanf("%d %d", &m, &k);

    if (!m) return 0;

    for (int i = 0; i < m; i++){
        scanf("%d", &a[i]);
    }

    makePrefix();
    memset(f, 0xff, sizeof(f));

    ans = search(m, k);
    printPlan();

    return 0;
}

代码（二分答案，CodeVS 3162，CodeVS 3168）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <utility>

using std::stack;
using std::pair;
using std::make_pair;

const int MAXM = 1000000;
const int MAXK = 10000;

int m, k;
int a[MAXM], prefix[MAXM], pageCount[MAXK], max;
int ans;

inline void makePrefix() {
    prefix[0] = a[0];
    for (int i = 1; i < m; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
}

inline int sum(int i, int j) {
    return i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
}

inline bool check(int limit) {
    memset(pageCount, 0, sizeof(pageCount));

    int j = k - 1, lastEnd = m - 1;
    for (int i = m - 1; i >= 0; i--) {
        if (pageCount[j] + a[i] <= limit) {
            pageCount[j] += a[i];
        } else {
            if (j == 0) {
                return false;
            }

            lastEnd = i;
            pageCount[--j] += a[i];
        }
    }

    return sum(0, lastEnd - 1) <= limit;
}

inline int binaryDivide() {
    int l = max, r = sum(0, m - 1);
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    return l;
}

inline void printPlan() {
    memset(pageCount, 0, sizeof(pageCount));

    int j = k - 1, lastEnd = m - 1;
    stack<pair<int, int> > s;
    for (int i = m - 1; i >= 0; i--) {
        if (j > i || pageCount[j] + a[i] > ans) {
            pageCount[--j] += a[i];
            s.push(make_pair(i + 1 + 1, lastEnd + 1));
            lastEnd = i;
        } else {
            pageCount[j] += a[i];
        }
    }

    printf("%d %d\n", 1, lastEnd + 1);
    while (!s.empty()) {
        pair<int, int> range = s.top();
        s.pop();
        printf("%d %d\n", range.first, range.second);
    }
}

int main() {
    scanf("%d %d", &m, &k);

    if (!m) return 0;

    for (int i = 0; i < m; i++){
        scanf("%d", &a[i]);
        max = std::max(max, a[i]);
    }

    makePrefix();

    ans = binaryDivide();
    printPlan();

    return 0;
}