题目大意
有一辆公交车，车上的人数恒非负。
有
n
n
n 次上下车。每次上下车都用一个整数
a
i
a_i
ai 来表示。若
a
i
a_i
ai 是正数，表示上了
a
i
a_i
ai 个人。否则表示下了
a
i
a_i
ai 个人。
车上初始的人数不确定。你需要找到一个初始人数，使得满足车上的人数恒非负的前提下，最终的人最少。输出最终车上的人数。
解题思路
遇到这种题目，首先想到是二分答案与递推，本蒟蒻太菜了，考场上没有想到递推，就直接二分答案了。我们给出二分范围
0
∼
1
0
18
0\sim 10^{18}
0∼1018，我们令
l
l
l 为二分范围下限，
r
r
r 为二分范围上限，
m
i
d
mid
mid 为
⌊
l
+
r
2
⌋
\lfloor\frac{l+r}{2}\rfloor
⌊2l+r⌋。对于每次操作，判断
m
i
d
mid
mid 是否合法，假如满足，我们就尝试找到更小的满足条件的答案，并将二分范围改为
l
∼
m
i
d
l\sim mid
l∼mid。否则，我们就去找更大的满足条件的答案，并将二分范围改为
m
i
d
+
1
∼
r
mid+1\sim r
mid+1∼r。在判断答案是否合法的时候，我们暴力判断就行了，时间复杂度为
O
(
n
l
o
g
1
0
18
)
O(n\ log\ 10^{18})
O(n log 1018)。
CODE：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200010];
ll t;
int n;
bool check(ll p) {
for (int i = 1; i <= n; i++) {
p += a[i];
if (p < 0)
return false;
}
t = p;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
ll l = 0, r = 1e18, k = 1e18;
while (l < r) {
ll mid = l + r >> 1;
if (!check(mid))
l = mid + 1;
else
r = mid, k = t;
}
cout << k;
return 0;
}
总结
这道题目应该算是二分板子吧，二分答案的思想运用广泛，在一些题目中可以率先尝试这种方法。