P1281 书的复制

P1281 书的复制 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

书按顺序给k个人，进行抄写，求抄写页数最多的人所用的时间的最小值。最大值最小，考虑二分。

又因为题目要求要尽可能让前面的人少抄写，那么就要求后面的多抄写，因此从后往前开始遍历。

二分用时最多的最小值这个答案，记作mid，从后往前开始判断，如果当前值加上这本书后的用时大于mid，则换另一个人进行抄书。如果可以，当且仅当当前抄写的人还有，且这个人抄写的值小于等于mid。

输出呢，照着二分中的check进行小小的修改即可。

void solve() {
    int n,m; cin>>n>>m;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i) cin>>a[i];
    int l = 0, r = 1e9;
    // 二分check
    auto check = [&](int mid) -> bool {
        int cnt = m, now = 0;
        for(int i = n; i >= 1; --i) {
            if(now + a[i] > mid) {
                now = a[i];
                --cnt;
            } else now += a[i];
        }
        return  cnt > 0 &&now <= mid;
    };
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    // 记录答案
    vector<array<int,2>> ans;
    int now = 0, st = n;
    for(int i = n; i >= 1; --i) {
        if(now + a[i] > r) {
            now = a[i];
            ans.push_back({i + 1, st});
            st = i;
        } else now += a[i];
    }
    // 存入第一个人的
    ans.push_back({1, st});
    // 翻转
    reverse(all(ans));
    for(auto &t: ans) cout<<t[0]<<" "<<t[1]<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38