题目链接
730. 机器人跳跃问题
机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 $N+1$ 座建筑——从 $0$ 到 $N$ 编号,从左到右排列。
编号为 $0$ 的建筑高度为 $0$ 个单位,编号为 $i$ 的建筑高度为 $H(i)$ 个单位。
起初,机器人在编号为 $0$ 的建筑处。
每一步,它跳到下一个(右边)建筑。
假设机器人在第 $k$ 个建筑,且它现在的能量值是 $E$,下一步它将跳到第 $k+1$ 个建筑。
如果 $H(k+1)>E$,那么机器人就失去 $H(k+1)−E$ 的能量值,否则它将得到 $E−H(k+1)$ 的能量值。
游戏目标是到达第 $N$ 个建筑,在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?
输入格式
第一行输入整数 $N$。
第二行是 $N$ 个空格分隔的整数,$H(1),H(2),…,H(N)$ 代表建筑物的高度。
输出格式
输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。
数据范围
$1≤N,H(i)≤10^5,$
输入样例1:
5
3 4 3 2 4
输出样例1:
4
输入样例2:
3
4 4 4
输出样例2:
4
输入样例3:
3
1 6 4
输出样例3:
3
解题思路
数学
设初始值为 $x$,则在第一个建筑后的能量为 $2x-H_1$,则:$x\geq\frac{H_1}{2}$,同理对于第二个建筑:$x\geq \frac{H_1}{2}+\frac{H_2}{4}$,则:$x\geq \frac{H_1}{2}+\frac{H_2}{4}+\dots +\frac{H_n}{2^n}$
- 时间复杂度:$O(n)$
代码
// Problem: 机器人跳跃问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/732/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int n;
int main()
{
double res=0;
cin>>n;
int base=2;
while(n--)
{
double h;
cin>>h;
res+=h/base;
base*=2;
if(base>1e9)break;
}
cout<<int(res+0.9999999);
return 0;
}