题目描述
机器猫出门斗恶龙了！他需要通过 𝑛 个关卡。
每个关卡要么是与怪物战斗，扣除一定的血量；要么是营地，给机器猫增加一定的血量。
在旅途中，机器猫任意时刻的血量不能低于或等于 0。问机器猫至少需要多少的初始血量，才能完成任务。
血量为正整数。
输入格式
第一行，一个正整数 𝑛n，表示关卡数量。
第二行，共 𝑛n 个整数 𝑎𝑖ai，表示每个关卡。
- 若 𝑎𝑖>0，则表示这个关卡是营地，增加 𝑎𝑖 的血量
- 若 𝑎𝑖<0，则表示这个关卡是战斗，机器猫血量代价为 𝑎𝑖
输出格式
仅一行，一个正整数，表示机器猫需要的初始血量。
#include <bits/stdc++.h>
using namespace std;int n, a[100005];void input() {cin >> n;for(int i = 1; i <= n; i++)cin >> a[i]; // a[i] 是血的变化量
}bool check(int x) { // 计算 x 点血是否可以活下来int hp = x;for(int i = 1; i <= n; i++){hp += a[i]; // hp增加或者减少if(hp <= 0) return false; // 如果活不下来返回 false}return true; // 如果可以活下来，返回 true
}
void work() {int l = 1, r = 1000 * 100000, mid;int ans = r;while(l <= r) {mid = (l + r) / 2;if(check(mid)) { // 检查mid血，发现可以活下来ans = mid; // 记录下答案r = mid - 1; // 继续找左区间} else // 如果发现活不下来l = mid + 1; // 继续找右区间}cout << ans << endl;
}int main() {input();work();return 0;
}