题解 | #小红的小踏前斩#

#include <cstdio>
#include <iostream>
#include <vector>
#include "bits/stdc++.h"
using namespace std;
const int maxn = 2e5+20;
int A[maxn];
using pr = pair<int, int>;
using ll  = long long;
int main() {
    int n;
    scanf("%d",&n);
    vector<pr>vec(n);
    for(int i =0;i<n;i++)  
    {
        int x;
        scanf("%d",&x);
        vec[i] = {x,i};
        A[i] = x;
    }
    /*
        1，两个怪相隔着，分开杀(砍他的前一个)
        2. 两个怪连着，一起杀
        (1)直接砍前一个，后面的也4
        (2)先砍这个把后一个砍4，然后再砍前一个，把他砍4
    */
    std::sort(vec.begin(),vec.end());
    //分开杀
    pr p1 = vec[0],p2 = vec[1];
    // printf("%d %d\n",p1.first,p2.first);
    ll ans = 2e18+10;
    ll sum = 0;
    if(p1.second!=0){
        sum+=(p1.first+1)/2;
    }
    else {
        if(n>2){
            pr p3 = vec[2];
            sum+=min((p3.first+1)/2,p1.first);
        }
        else{
            sum+=p1.first;
            // printf("%lld\n",sum);
        }
    }
    if(p2.second!=0){
        sum+=(p2.first+1)/2;
                    // printf("%lld\n",sum);
    }
    else {
        if(n>2){
            pr p3 = vec[2];
            sum+=min((p3.first+1)/2,p2.first);
        }
        else{
            sum+=p2.first;
        }
    }
    ans = min(ans,sum);
    // printf("%lld\n",ans);
    //连着鲨
    for(int i = 1;i<n-1;i++){
        //砍他妈的，然后把后面的也砍死
        // int tmp=0;
        ll tmp1 = max(A[i],(A[i+1]+1)/2);
        //先把他后面那个砍死，再用上一个把i砍死   
        ll tmp2 = (A[i+1]+1)/2;
        int ai =A[i]-tmp2;
        tmp2+=max((ai+1)/2,0);
        ans = min(ans,min(tmp1,tmp2));
    }
    //第一个只有直接砍死
    ans = min(ans,1LL*max(A[0],(A[1]+1)/2));
    printf("%lld\n",ans);


}