贪心/时间复杂度O(n)
由E(n) = 2 * E(n - 1) - h[n],若E(n) = 0,因h[n] > 0,故E(n - 1)必定大于零,递推可知任意一个状态都大于零,而E(0)越大E(n)越大,所以E(n)最小(=0)时得到最优解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int height[N];
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &height[i]);
int ans = 0;
for (int i = n - 1; i >= 0; --i)
{
ans = ans + height[i] + 1 >> 1;
}
printf("%d", ans);
return 0;
}
二分答案/时间复杂度O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int height[N];
int n;
bool check(int e)
{
for (int i = 0; i < n; ++i)
{
e = 2 * e - height[i];
if (e >= 100000) return true;
if (e < 0) return false;
}
return true;
}
int main()
{
scanf("%d", &n);
int l = 1, r = 1;
for (int i = 0; i < n; ++i)
{
scanf("%d", &height[i]);
r = max(r, height[i]);
}
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l <<endl;
return 0;
}