小红的小踏前斩

#python代码
#踏前斩最小数量：分两种情况讨论，两个相邻的怪物或者最小血量的两个怪物
#核心思想：1.如果第二个怪物的血量大于第一个怪物血量的两倍，如2,5，这时最小次数主要看
#第二个怪物的血量，最小次数为(5+1)//2
#2.如果第二个怪物的血量小于等于第一个怪物血量的两倍，如2,3，这时首先对第一个怪物释放
#技能（因为这样可以同时打到两个怪物），第二个怪物死后，为消灭第一个怪物，对第一个怪
#物的前一个怪物释放技能打死第一个怪物。
#注意i==0时要分类讨论
#求最小的两个值时，首先给min1赋值为a[0]，因为后面循环i从0变到n-2，那么（i+1）刚好就
#是除了第一个元素之外的n-1个元素
n = int(input())
a = list(map(int,input().split()))
min1 = a[0]
min2 = float('inf') 
ans = float('inf')
for i in range(n-1):
    if i == 0:
        if a[1] <= 2*a[0]:
            count = a[0]
        else:
            count = (a[1]+1)//2
    else:
        if a[i+1] > 2*a[i]:
            count = (a[i+1]+1)//2
        else:
            count = (a[i+1]+1)//2+(a[i]-(a[i+1]+1)//2+1)//2
    ans = min(ans,count)
    m = (a[i+1]+1)//2    #求杀死a[i+1]怪兽的最小踏前斩次数
    if m < min1:
        min2 = min1
        min1 = m
    elif m < min2:
        min2 = m
print(min(ans,min1+min2))

枚举法

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

int getDeadCnt(int val, int idx) {
    if (val <= 0) return 0;
    else if (idx == 0) return val;
    else return (val / 2 + (val % 2));
}

int main() {
    int n;
    cin >> n;
    vector<int64_t> v(n, 0);
    for (auto& e : v) cin >> e;
    int ret = v[0] + v[1];
    int idx = 0;
    for (int i = 1; i < v.size(); ++i) {
        int cnt = getDeadCnt(v[i], i);
        int preCnt = getDeadCnt(v[i - 1] - cnt, i - 1);
        int tmpCnt = preCnt;
        if (idx < i - 1) {
            if (idx == 0) tmpCnt = v[idx];
            else tmpCnt = v[idx] %2 + v[idx]/2;
        }
        ret = min(ret, cnt + min(preCnt, tmpCnt));
        if (v[idx] >= v[i]) idx = i;
    }
    std::cout << ret << std::endl;
}
// 64 位输出请用 printf("%lld")

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int len = in.nextInt();
        int[] nums = new int[len];
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;

        for (int i = 0; i < len; i++) {
            nums[i] = in.nextInt();
        }
        int res = Integer.MAX_VALUE;

        for (int i = 1; i < len; i++) {
            // 求两个最小值，不包含数组第一个元素
            if (nums[i] < min2) {
                if (nums[i] < min1) {
                    min2 = min1;
                    min1 = nums[i];
                } else {
                    min2 = nums[i];
                }
            }

            // 杀死相邻两个怪物，需要的最少次数
            // 杀死当前怪物 i
            int right = (nums[i] + 1)/ 2;
            // 杀死前一个怪物 i-1
            int left = nums[i - 1];
    
            if (right >= left) {
                res = Math.min(res, right);
            } else if (left > right) {
                if (i > 1) {
                    res = Math.min(res, right + ((left - right + 1) / 2));
                } else {
                    res = Math.min(res, left);
                }
            }
        }

        int tmp = 0;
        if (nums[0] < (min2 + 1) / 2) {
            tmp = (min1 + 1) / 2 + nums[0];
        } else {
            tmp = (min1 + 1) / 2 + (min2 + 1) / 2;
        }
        
        System.out.println(Math.min(tmp, res));
    }
}