#include <vector>
#include <iostream>
#include <math.h>

class Solution { 
public:
  static void solve(const std::vector<int>& data) { 
    
    // need:到达终点的所需要最小的能量
    int need=0; 

    /**
     * @brief: 到达终点能量为0时，开始所需能量最小。
     *         从终点开始倒推理，推理出前一步所需的能量。
     *         一直递推到起点
     * 
     * 为什么需要 ceil(...)？ 
     * 
     * 因为会出现 (*iter + need) 为奇数，如果不向上取整，就会少1，最后到终点时不是0，而是-1
     * 
     * 比如，输入如下：
     * 
     *  3
     *  3 2 4
     * 
     *  正确结果是3，但是实际上输出2，就是因为没有向上取整。
    */
    for(auto iter=data.rbegin(); iter != data.rend(); ++iter) { 
      need = ::ceil(static_cast<float>((*iter + need)) / 2); // 向上取整
    }

    std::cout<<need<<std::endl;;
  }
};

int main(int argc, char const *argv[]) {

  int N=0;
  std::cin>>N;
  std::vector<int> data(N);

  for(int i=0; i < N; ++i) { 
    std::cin>>data[i];
  }

  Solution::solve(data);

  return 0;
}
对一个前排大佬的代码的一点注释。牛客网的markdown***，本想发在评论里，但是没有格式了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL n;
LL a[100010];

int main()
{
    cin>>n;
    LL r=0;
    for(LL i=0;i<n;i++) 
    {
        scanf("%lld",&a[i]);
        r=max(r,a[i]);
    }
    
    LL l=0;
    while(l<r)
    {
        LL mid=l+r>>1;
        LL sum=mid;
        for(LL i=0;i<n;i++)
        {
            sum+=(sum-a[i]);
            if(sum<0)
            {
                l=mid+1;
                break;
            }
            else if(sum>1e5) break;
        }
        
        if(sum>=0) r=mid;
    }
    
    cout<<l<<endl;
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,e=0;
    cin>>n;
    int h[n];
    for(int i=0;i<n;i++)
        cin>>h[i];
    for(int i=n-1;i>=0;i--)
        e = (e+h[i]+1)>>1;
    cout<<e<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int main() {
    int N;
    cin >> N;
    vector<long double> hs(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> hs[i];
    }
    long double res = 0;
    for (int i = N; i >= 1; --i) {
        res = (res + hs[i]) / 2;
    }
    cout << ceil(res) << endl;
    return 0;
}

二分

n = int(input())
high = list(map(int, input().split()))

left, right = 0, max(high)

def fun(power):
    for i in range(n):
        if power > high[i]:
            power += power - high[i]
        else:
            power -= high[i] - power
        if power < 0:
            return False
    return True

while left < right:
    mid = (left + right) >> 1
    if fun(mid):
        right = mid
    else:
        left = mid + 1

print(left)

import math n = int(input()) h = [0]+list(map(int, input().split())) E = [0]*(n+1) for i in range(n-1,-1,-1):  E[i] = (E[i+1]+h[i+1])*0.5 print(math.ceil(E[0]))

import math

n = int(input())
H = [int(i) for i in input().split()]
E0 = 0
for i in range(n):
    E0 += H[i] / 2**(i+1)
print(math.ceil(E0))

由题干描述可以得出：

进而归纳得出：

令所有的，则需满足：

求得：

从后往前逆推

#include<iostream>
#include<vector>
 #include<cmath>
 using namespace std;
 int main(){
 int N;
 int ans = 0;
 cin >> N;
 vector<int>D(N,0);
 for(int i = 0;i<N;i++)
 cin >>D[i];
 for(int j=N-1;j>=0;j--){
 ans = ceil((D[j]+ans)/2.0);//注意c++中除法整数/整数为0，ceil向上取整要整数/float类型
 }
 cout<<ans<<endl;
 return 0;
 }

input()
arr = list(map(int, input().split(' ')))
# 假设跳跃前能力为E,要跳的高度为H，那么跳跃后的能量就是2E-H，
# 那么跳跃后的能量加上高度就是跳跃前的两倍，然后从后往前逆推。
E = 0    # 跳到最后一步的能力值设为0
arr.reverse()
for H in arr:
    E = (E + H + 1) >> 1
print(E)

此题用java来解决有点坑，从题面上来看简单的使用二分法就能得出答案，但是在运行的时候
总是只能ac百分之几，同样的代码用python可以很简单的通过，找了半天没有找到原因。后来debug才发现，
在能量够大的情况下一直累加导致long型数据超出界限。只要加上一句
if(num > 500000){return true；}，即可。因为当能量达到500000时，即便后面不可能再使能量减少，此时必定符合要求。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int left = 1;int right = 100000;
        Main main = new Main();

        while(right > left +1){
            int mid = (right + left) / 2;

            if(main.isPass((long)mid,a)){
                right = mid;
            }else{
                left = mid;
            }
        }
        if(main.isPass(left,a)){
            System.out.println(left);
        }else {
            System.out.println(right);
        }

    }
    public boolean isPass(long num,long[] a){
        for(int i=0;i<a.length;i++){
            if(num <= a[i]){
                num -= a[i] - num;
            }else{
                num += num -a[i];
            }
            if(num > 500000){
                return true;
            }
            if (num < 0){
                return false;
            }
        }
        return true;
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                int n = scanner.nextInt();
                scanner.nextLine();
                int[] a =new int[n];
                long sum=0;
                for(int i = 0 ;i<n;i++){
                        a[i] = scanner.nextInt();
                        sum = Math.max(sum,a[i]);
                }
                long low = 0;
                long high = sum;
                long mid = 0;
                while (low<=high){
                        mid = (low+high)/2;
                        if(check(a,mid)){
                                high = mid-1;
                        }else
                                low = mid+1;
                }
                System.out.println(low);

        }
        public static boolean check(int[] a,long e){
                int maxm=0;
                for(int i = 0;i<a.length;i++){
                        maxm = Math.max(maxm,a[i]);
                }
                for(int i = 0;i<a.length;i++){
                        if(e>maxm)
                                return true;
                        if(e<a[i]){
                                e -=a[i]-e;
                        }else{
                                e+=e-a[i];
                        }
                        if(e<0)
                                return false;
                }
                return true;
        }
}

机器人跳跃问题

题目分析：

1）机器人有一定的能量，要想跳过前方的所有障碍，所需能量的最小值

2）能找到一种 (正/负)相关 的相关关系：

==》机器人所固有的能量越高，越能越过前方障碍

3）固有能量 和 能否越过障碍 之间的关系 的证明：

eg: 机器人名字(能量)、柱高：value

两个机器人：A(x) 、B(y) (x < y)

1） 遇到小于或等于自己能量的柱子：高能量机器人更具优势

value <= x < y：

对于 A：能量增幅(A_UP) 为 (x - value)

对于 B：能量增幅(B_UP) 为 (y - value)

明显：B_UP > A_UP

2） 遇到大于等于自己能量的柱子：高能量机器人更具优势

x < y <= value：

对于 A：能量减幅(A_DOWN) 为 (value - x)

对于 B：能量减幅(B_DOWN) 为 (value - y)

明显：A_DOWN > B_DOWN

3） 遇到 A 、B 机器人能量中间的柱子：高能量机器人更具优势

x < value < y：

对于 A：能量减幅(A_DOWN) 为 (value - x)

对于 B：能量增幅(B_UP) 为 (value - y)

明显：高能量机器人能量增加，低能量机器人能量减少

4）可以画二分图：

相关代码和注释：

#include<bits/stdc++.h>

using namespace std;

// 看看以当前能量：energy，能否越过前方所有柱子
bool f(int energy , const vector<int>& pillars , int maxx)
{
    for(const auto& e : pillars)
    {
        // 遇到小于等于自己能量的柱子：能量增加
        if(e<= energy)
        {
            energy += (energy - e);
        }
        // 遇到大于自己能量的柱子：能量减少
        else
        {
            energy -= (e - energy);
        }

        // 合理剪枝：当某阶段能量大于最高柱子时，一定能够能通过，不用再计算
        if(energy >= maxx)
        {
            return true;
        }

        // 合理剪枝的必要性：
        // eg: 1 1 1 ... 1 1   1 
        //     0 1 2 ... n n+1 n+2
        // 依次跳过这些柱子的能量变化(energy = 2)：
        // energy + 1 + 2 + 4 + 8 + ... 
        // energy 以 2 的指数形式增加，不出几个柱子就会导致 energy 的值超过 long long 类型
        //所以一定要剪枝

        // 合理剪枝：当某阶段的能量小于0，一定不能够通过前方的所有柱子，不用再计算
        if(energy < 0)
        {
            return false;
        }

        // 如果能量：0 < energy <= max(pillars[i]) ，继续计算，正常跳下去
    }

    // 0 < energy <= max(pillars[i])
    // 通过了所有柱子，返回true
    return true;
}

int main()
{
    int n=0;
    vector<int> pillars;
    pillars.clear();
    scanf("%d" , &n);

    for(int i=0 ; i<n ; i++)
    {
        int x;
        scanf("%d" , &x);
        pillars.push_back(x);
    }

    // 能量值范围 [0 , max(pillars[i])]
    int maxx = pillars[0];
    for(const auto& e : pillars)
    {
        maxx = max(maxx , e);
    }

    int l=0 , r = maxx;
    int ans=0;

    // 进行二分
    while(l<=r)
    {
        // 防止溢出的一种写法：
        int mid = l + ((r-l)>>1);

        // 看看此时的 energy 能否通过前方所有柱子
        // 如果能，记录答案，并想能量值小的方向看，看看还有没有更小的能过通过所有柱子的答案
        if(f(mid , pillars , maxx))
        {
            ans = mid;
            r = mid - 1;
        }
        // 如果不能通过所有柱子，向能量稍微大一点的方向看
        else
        {
            l = mid+1;
        }
    }

    cout << ans << endl;

    return 0;
}