C++
$\color{gold}{— > 蓝桥杯辅导课题解}$
思路:
$\color{red}{二分}$
$在[0, 1e5]这个区间进行二分,从而找到最小符合条件的能量值$
$图解:$
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N];
bool check(int e) {
for (int i = 1; i <= n; i ++) {
if (h[i] > e)
e -= h[i] - e;
else
e += e - h[i];
//e = e * 2 - h[i];
if (e > 1e5) return true;
/*
关于为什么 e > 1e5 可以直接返回true?
e 是这样不断变化的:e = e * 2 - h[i];
= e + e - h[i]
当 e > 1e5 时,由于h[i]的最大值是等于1e5,
故当e > 1e5时,之后e一定是递增的,不会小于0了,
所以当e > 1e5 时,直接返回true即可
*/
if (e < 0) return false;
}
return true;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> h[i];
int l = 0, r = 1e5;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}