C++: 自动刷题机 - SHOI2015 - 常规

C++: 自动刷题机 - SHOI2015

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。

题目描述

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

写了 x 行代码
心情不好，删掉了之前写的 y 行代码。（如果 y 大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的正整数长度 n，一旦自动刷题机在某秒结束时积累了大于等于 n 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 n 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 k 道题，希望你计算 n 可能的最小值和最大值。

输入格式

第一行两个整数 l , k，表示刷题机的日志一共有 l 行，一共了切了 k 题。

接下来 l 行，每行一个整数 x_i，依次表示每条日志。若 x_i >= 0，则表示写了 x_i 行代码，若 x_i < 0，则表示删除了 -x_i 行代码。

输出格式

输出一行两个整数，分别表示 n 可能的最小值和最大值。如果这样的 n 不存在，请输出一行一个整数 -1。

样例 #1

样例输入 #1

样例输出 #1

3 7

提示

数据规模与约定

对于 20% 的数据，保证 l <= 10；
对于 40% 的数据，保证 l <= 100 ；
对于 60% 的数据，保证 l <= 2 * 10^3；
对于 100% 的数据，保证 1 <= l <= 10^5，-10^9 <= x_i <= 10^9。

思路

根据题目描述，我们可以使用二分查找的方法来找到可能的最小值和最大值。

首先，我们可以观察到，对于某个确定的自动刷题机的操作序列，如果我们设置的 n 小于等于实际操作序列的长度，那么至少会有一次提交成功。因此，最小值一定不会小于操作序列的长度。

接下来，我们假设最小值为 n，然后模拟自动刷题机的操作序列。每次遇到写代码的操作，我们就将写的行数加到当前长度上；每次遇到删除代码的操作，我们就将删除的行数从当前长度中减去。当当前长度大于等于 n 时，我们就认为此时自动刷题机可以提交并 AC 此题，并重置当前长度为 0，开始下一题。如果在模拟操作序列的过程中，自动刷题机成功提交了 k 题，那么我们就认为最小值为 n 是可能的。

我们可以使用二分查找的方法来找到最小值。初始时，最小值的下界为操作序列的长度，上界为操作序列的总行数。然后，我们计算中间值 mid，并模拟自动刷题机的操作序列，看是否可以成功提交 k 题。如果可以，则将上界更新为 mid；如果不可以，则将下界更新为 mid+1。直到最小值的下界大于等于上界为止，此时的上界就是最小值。

接下来，我们需要找到最大值。我们可以观察到，自动刷题机的操作序列中，每个题目的提交次数是不会超过 n 次的，因为一旦提交了 n 行代码，就会重置当前长度为 0，开始下一题。因此，最大值一定不会超过操作序列的总行数。

我们可以使用二分查找的方法来找到最大值。初始时，最大值的下界为操作序列的长度，上界为操作序列的总行数。然后，我们计算中间值 mid，并模拟自动刷题机的操作序列，看是否可以成功提交 k 题。如果可以，则将下界更新为 mid；如果不可以，则将上界更新为 mid-1。直到最大值的下界大于等于上界为止，此时的下界就是最大值。

最后，我们输出最小值和最大值作为答案。

代码实现

#include <iostream>
#include <vector>
using namespace std;

bool simulate(vector<int>& logs, int n, int k) {
    int currLen = 0;
    int numSubmits = 0;
    for (int i = 0; i < logs.size(); i++) {
        if (logs[i] >= 0) {
            currLen += logs[i];
            if (currLen >= n) {
                numSubmits++;
                currLen = 0;
            }
        } else {
            currLen += logs[i];
            if (currLen < 0) {
                currLen = 0;
            }
        }
    }
    return numSubmits >= k;
}

int main() {
    int l, k;
    cin >> l >> k;

    vector<int> logs(l);
    for (int i = 0; i < l; i++) {
        cin >> logs[i];
    }

    int minLen = l;
    int maxLen = 0;

    // Find minLen
    int left = l;
    int right = l * l;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (simulate(logs, mid, k)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    minLen = right;

    // Find maxLen
    left = l;
    right = l * l;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (simulate(logs, mid, k)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    maxLen = right;

    if (minLen > maxLen) {
        cout << -1 << endl;
    } else {
        cout << minLen << " " << maxLen << endl;
    }

    return 0;
}

该算法的时间复杂度为 O(l log(l))，其中 l 是操作序列的长度。