题目理解

我们有一个自动刷题机，它的工作方式如下：

• 每秒执行一个操作：写 $x$ 行代码（$x \geq 0$）或删除 $|x|$ 行代码（$x < 0$）
• 当代码行数 $\geq n$ 时，自动提交并清空代码
• 已知操作序列和总AC题数 $k$，求 $n$ 的可能取值范围

---

问题分析

1. 关键观察

对于给定的 $n$，我们可以模拟整个过程来计算AC的题数：

• 从代码行数 $0$ 开始
• 依次处理每个操作：
  • 如果是正数：增加代码行数
  • 如果是负数：减少代码行数（不低于 $0$）
• 当代码行数 $\geq n$ 时：AC数 $+1$，代码行数归 $0$

2. 问题转化

我们需要找到所有满足条件的 $n$，使得模拟后AC题数恰好等于 $k$。

设 $f(n)$ 表示阈值为 $n$ 时的AC题数，则：

• 求最小的 $n$ 使得 $f(n) = k$
• 求最大的 $n$ 使得 $f(n) = k$

---

单调性分析

重要性质：$f(n)$ 关于 $n$ 是单调不增的。

• 当 $n$ 增大时，更难达到提交阈值
• 因此AC题数不会增加

这意味着：

• 如果 $f(n) = k$，那么所有满足条件的 $n$ 构成一个连续区间
• 我们可以用二分查找来找到这个区间的左右边界

---

二分查找设计

1. 检查函数

long long check(long long n, const vector<int>& ops) {
    long long current = 0;  // 当前代码行数
    long long ac_count = 0; // AC题数
    
    for (int x : ops) {
        current += x;
        if (current < 0) current = 0;  // 代码行数不会为负
        if (current >= n) {
            ac_count++;
            current = 0;  // 提交后清空
        }
    }
    return ac_count;
}

2. 查找最小n

我们要找满足 $f(n) \leq k$ 的最大 $n$？等等，需要仔细分析：

实际上：

• 当 $n$ 太小时，$f(n) > k$（AC太多）
• 当 $n$ 合适时，$f(n) = k$
• 当 $n$ 太大时，$f(n) < k$（AC不够）

所以：

• 最小n：满足 $f(n) = k$ 且 $f(n-1) > k$（如果存在）
• 最大n：满足 $f(n) = k$ 且 $f(n+1) < k$

---

二分查找实现

查找最小n：

long long left = 1, right = 1e18;  // 二分范围
long long min_n = -1;

while (left <= right) {
    long long mid = left + (right - left) / 2;
    long long cnt = check(mid, ops);
    
    if (cnt <= k) {
        if (cnt == k) min_n = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

查找最大n：

left = 1, right = 1e18;
long long max_n = -1;

while (left <= right) {
    long long mid = left + (right - left) / 2;
    long long cnt = check(mid, ops);
    
    if (cnt >= k) {
        if (cnt == k) max_n = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

---

边界情况处理

1. 无解情况

如果 $min_n = -1$ 或 $max_n = -1$，输出 $-1$

2. 数据范围

• $n$ 的下界：$1$（题目保证 $n > 0$）
• $n$ 的上界：最大可能为所有正操作的和（但可能更大）
• 使用 $10^{18}$ 作为二分上界是安全的

---

复杂度分析

• 检查函数：$O(l)$
• 二分查找：$O(\log (10^{18})) \approx O(60)$
• 总复杂度：$O(60 \times l)$，对于 $l \leq 10^5$ 可接受

---

样例验证

输入：

4 2
2
5
-3
9

操作序列：$[2, 5, -3, 9]$

验证不同 $n$ 值：

• $n = 2$：过程：

  • +2 = 2 ≥ 2 → AC=1, 清0
  • +5 = 5 ≥ 2 → AC=2, 清0
  • -3 = 0
  • +9 = 9 ≥ 2 → AC=3 结果：AC=3 > 2

• $n = 3$：过程：

  • +2 = 2 < 3
  • +5 = 7 ≥ 3 → AC=1, 清0
  • -3 = 0
  • +9 = 9 ≥ 3 → AC=2 结果：AC=2 = 2 ✓

• $n = 7$：过程：

  • +2 = 2 < 7
  • +5 = 7 ≥ 7 → AC=1, 清0
  • -3 = 0
  • +9 = 9 ≥ 7 → AC=2 结果：AC=2 = 2 ✓

• $n = 8$：过程：

  • +2 = 2 < 8
  • +5 = 7 < 8
  • -3 = 4 < 8
  • +9 = 13 ≥ 8 → AC=1 结果：AC=1 < 2

所以 $n$ 的范围是 $[3, 7]$，输出 3 7 ✓

---

算法总结

本题的关键在于：

1. 发现 $f(n)$ 的单调性
2. 使用二分查找确定满足条件的 $n$ 的范围
3. 注意二分查找时边界条件的处理
4. 模拟过程要正确处理代码行数的变化

这是一个典型的二分答案问题，通过将原问题转化为判定问题来求解。