[SHOI2015] 自动刷题机

题意

自动刷题机每天会按照日志修改代码行数：

正数表示新增若干行
负数表示删除若干行，删过头就变成 0

若某一秒结束时代码长度达到某个未知阈值 n，就会立刻 AC 一题，并把代码清空重新开始。

现在已知整天一共 AC 了 k 题，要求求出这个阈值 n 可能的最小值和最大值。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 205;

int l, target_k;
i64 a[MAXN];

int count_ac(i64 need) {
    i64 cur = 0;
    int cnt = 0;

    for (int i = 1; i <= l; i++) {
        cur += a[i];
        if (cur < 0) cur = 0;
        if (cur >= need) {
            cnt++;
            cur = 0;
        }
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> target_k;
    i64 sum_pos = 0;
    for (int i = 1; i <= l; i++) {
        cin >> a[i];
        if (a[i] > 0) sum_pos += a[i];
    }

    i64 first = -1;
    i64 last = -1;

    for (i64 n = 1; n <= sum_pos; n++) {
        if (count_ac(n) == target_k) {
            if (first == -1) first = n;
            last = n;
        }
    }

    if (first == -1) cout << -1 << '\n';
    else cout << first << ' ' << last << '\n';

    return 0;
}

固定阈值 n 后，这题就只剩一件事：

按日志模拟整天最后能 AC 几题

设这个函数为 count(n)。

模拟规则非常直接：

当前代码长度加上这秒的变化量
若小于 0，就归零
若达到 n，就 AC 一题，并把当前代码长度清零

关键观察在于：

n 越大，达到阈值越难
所以 count(n) 随 n 增大单调不增

于是所有满足：

count(n) = k

的整数 n 一定构成一个连续区间。

因此只需要二分两次：

找最小的 n，使 count(n) <= k
找最大的 n，使 count(n) >= k

如果左端点处 count(n) 都不是 k，说明根本不存在这样的阈值，输出 -1。

代码

cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 100000 + 5;

int l;
int target_k;
i64 a[MAXN];

int count_ac(i64 need) {
    i64 cur = 0;
    int cnt = 0;

    for (int i = 1; i <= l; i++) {
        cur += a[i];
        if (cur < 0) cur = 0;

        if (cur >= need) {
            cnt++;
            cur = 0;
        }
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> target_k;
    i64 max_prefix = 0;
    i64 cur = 0;
    for (int i = 1; i <= l; i++) {
        cin >> a[i];
        cur += a[i];
        if (cur < 0) cur = 0;
        if (cur > max_prefix) max_prefix = cur;
    }

    // 找最小的 n，使 count_ac(n) <= k。
    i64 left = 1, right = max_prefix + 1;
    while (left < right) {
        i64 mid = (left + right) >> 1;
        if (count_ac(mid) <= target_k) right = mid;
        else left = mid + 1;
    }
    i64 min_n = left;

    if (count_ac(min_n) != target_k) {
        cout << -1 << '\n';
        return 0;
    }

    // 找最大的 n，使 count_ac(n) >= k。
    left = 1, right = max_prefix + 1;
    while (left < right) {
        i64 mid = (left + right + 1) >> 1;
        if (count_ac(mid) >= target_k) left = mid;
        else right = mid - 1;
    }
    i64 max_n = left;

    cout << min_n << ' ' << max_n << '\n';
    return 0;
}

复杂度

一次模拟是 $O(l)$ ，二分两次总复杂度是 $O(l log V)$ ，其中 V 是阈值上界。

总结

这题最重要的是把原问题抽象成一个单调函数：

count(n)：阈值为 n 时能 AC 的题数

一旦看到它单调不增，后面就是很标准的“模拟 + 二分区间端点”。

[SHOI2015] 自动刷题机

目录

题意

思路

代码

复杂度

总结