Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


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

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

链接

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

划分 DP

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

边界条件为:

f[m][1]=i=1na[i]f[m][1]={\sum_{i=1}^{n}}a[i]

转移方程为:

f[m][k]=min{max(f[i][k1],j=i+1ma[j]),i[k1,m1]}f[m][k]={\min} \{ {\max}(f[i][k-1],{ \sum_{j=i+1}^{m}}a[j]), i{\in}[k-1,m-1]\}

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

求书本页数的区间和可以用一个前缀和数组来优化时间复杂度,故该算法时间复杂度为 O(km2)O(km^2)

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 的方法,考虑对最短时间在最大页数总页数之间进行二分,检验过程贪心枚举每一本书,从最后一个人开始,如果当前的人还能抄就给他抄,否则给前一个人抄,如果最后能抄完则可行。

时间复杂度为 O(mlogm)O(m{\log}m)

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;
}