X016 机器猫斗恶龙
大约 2 分钟
X016 机器猫斗恶龙
【算法】 二分答案
【C++】 二分、模拟验证
【难度】 普及−
一、题目简述
有 个关卡,每个关卡有一个整数 :正数表示加血,负数表示扣血。角色按顺序通过所有关卡,任意时刻血量不能 ≤ 0(即血量必须始终保持 ≥ 1)。求所需的最少初始血量。
数据范围:,。
二、解题思路
1. 问题本质
这是一个"可行性判定"问题:给定初始血量,能否成功通关?要在所有可行的初始血量中找到最小的那个。
2. 为什么能用二分
单调性:初始血量 越大,角色越容易存活。如果初始血量为 时能通关,那么任何大于 的初始血量也一定能通关。反之,如果 不能通关,任何小于 的初始血量也不能通关。
这种"能/不能"的判定在某个值上发生切换(左边全不能,右边全能),满足二分的条件。
3. check 函数设计
check(mid):从初始血量 mid 出发,依次模拟每个关卡:
cur += a[i]- 若某一步后
cur ≤ 0,说明中途死亡,返回false - 若能走到最后,返回
true
注意血量可能很大(比如一直加血),需要用 long long。
4. 二分范围
- 左边界:(血量至少为 1)
- 右边界:所有扣血量的总和 + 1(最坏情况下,把所有扣血都扛下来)
5. 手动模拟
以数组 [-200, -300, 1000, -100, -100] 为例:
| 初始血量 | 过程 | 结果 |
|---|---|---|
| 500 | 500→300→0(死亡) | ❌ |
| 501 | 501→301→1→1001→901→801 | ✅ |
| 600 | 600→400→100→1100→1000→900 | ✅ |
最小初始血量 = 501。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], n;
bool check(long long mid) {
long long cur = mid;
for (int i = 1; i <= n; i++) {
cur += a[i];
if (cur <= 0) return false;
}
return true;
}
int main() {
cin >> n;
long long sumNeg = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] < 0) sumNeg += -a[i];
}
long long l = 1, r = sumNeg + 1, ans = r;
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) { ans = mid; r = mid - 1; }
else l = mid + 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是所有扣血量的总和(即二分范围)。每次
check需要遍历 个关卡,二分约 次。 - 空间复杂度:,存储关卡数组。
