C++# SHOI2015 自动刷题机## 题目背景曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。## 题目描述自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法然后开始写程序。每秒自动刷题机的代码生成模块会有两种可能的结果：1写了 $x$ 行代码 2心情不好删掉了之前写的 $y$ 行代码。如果 $y$ 大于当前代码长度则

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

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

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

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

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

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

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

下面是使用 C++ 实现的代码：

#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$ 是操作序列的长度