P4343 [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 \geq 0\)，则表示写了 \(x_i\) 行代码，若 \(x_i \lt 0\)，则表示删除了 \(-x_i\) 行代码。
输出格式
输出一行两个整数，分别表示 \(n\) 可能的最小值和最大值。
如果这样的 \(n\) 不存在，请输出一行一个整数 \(-1\)。
输入输出样例 #1
输入 #1
4 2
2
5
-3
9
输出 #1
3 7
说明/提示
数据规模与约定
- 对于 \(20\%\) 的数据，保证 \(1 \le l \le 10\)；
- 对于 \(40\%\) 的数据，保证 \(1 \le l \le 100\) ；
- 对于 \(60\%\) 的数据，保证 \(1 \le l \le 2 \times 10^3\)；
- 对于 \(100\%\) 的数据，保证 \(1 \leq l \le 10^5\)，\(-10^9 \le x_i \le 10^9\)，\(k\) 在
int存储范围内。
题解
这题想到二分答案后，其实思路上就不难了，主要是代码实现细节比较难Debug了好久哭😭。
点击查看AC代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;int n, k;
ll a[N];bool check(ll mid, ll k){ll su = 0;for(int i = 1; i <= n; i++){su += a[i];if(su < 0){ su = 0; continue; }if(su >= mid){ k--; su = 0; }}return k > 0;
}void solve(){cin >> n >> k;for(int i = 1; i <= n; i++) cin >> a[i];if(k == n){ // test 4ll lans = 1, mn = 1e9;for(int i = 1; i <= n; i++)mn = min(a[i], mn);if(mn > 0) cout << lans << ' ' << mn << '\n';else cout << -1 << '\n';return;}ll l = 0, r = 1e14;while(l < r){ll mid = (l + r) >> 1;if(check(mid, k)) r = mid;else l = mid + 1;}ll ansr = r;l = 0; r = 1e14;while(l < r){ll mid = (l + r) >> 1;if(check(mid, k + 1)) r = mid;else l = mid + 1;}if(ansr <= 1 || check(ansr - 1, k) || check(r, k)){ cout << -1 << '\n'; return ; }cout << r << " " << ansr - 1 << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);solve();return 0;
}