题目描述

blablabla

样例

blablabla

算法1

贪心的思路，倒序往前推最小需要的量

假设在h[i]时能量为E[i],那么无论h[i+1]是否大于或者小于E[i],最后跳到h[i+1]时的能量计算公式都是E[i+1]=2E[i]-h[i+1],那么反推回来如果这知道h[i+1]处的能量E[i+1]，那么他所需要的前面的h[i]处的能量就是E[i]=(E[i+1]+h[i+1])/2;

那么我们令机器人跳到最后一格时正好剩余能量为0，那么以此往前推导即可，注意要上取整

时间复杂度 O(n)

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N=1e5+10;
int h[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];

    int e=0;
    for(int i=n;i;i--)  e=(e+h[i]+1)/2;

    cout<<e<<endl;

    return 0;
}