B3628 机器猫斗恶龙

题目描述

机器猫出门斗恶龙了！他需要通过 𝑛 个关卡。

每个关卡要么是与怪物战斗，扣除一定的血量；要么是营地，给机器猫增加一定的血量。

在旅途中，机器猫任意时刻的血量不能低于或等于 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;
}