BZOJ4590 [SHOI2015] 自动刷题机

Description

一个自动刷题机,每次有两种操作:写下\(x\)行代码或删除\(x\)行代码(不足则全部删除)。存在一个\(n\),每当代码量大于等于\(n\)时将提交一次并把代码全部删除。已知每次的操作类型和\(x\),已知一共提交了\(k\)次,问\(n\)的最大值和最小值。

Solution

可以证明\(n\)增大时提交次数不减。于是二分即可。

Code

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
#include <algorithm>
#include <cstdio>
typedef long long LL;
const int N = 100050;
int x[N], n, k;
int calc(LL m) {
int ans = 0;
for (LL i = 0, t = 0; i < n; ++i)
if ((t = std::max(t + x[i], 0LL)) >= m)
++ans, t = 0;
return ans;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) scanf("%d", &x[i]);
if (calc(1) < k) return puts("-1") & 0;
LL l = 1, r = 1e15;
while (l < r) {
LL mid = (l + r) / 2;
if (calc(mid) > k) l = mid + 1;
else r = mid;
}
if (calc(l) != k) return puts("-1") & 0;
printf("%lld ", l);
l = 1, r = 1e15;
while (l < r) {
LL mid = r + (l - r) / 2;
if (calc(mid) < k) r = mid - 1;
else l = mid;
}
printf("%lld\n", l);
return 0;
}