高岭华

takanashi_mifuru · 2025-01-02 17:01:22 · 题解

考虑先打个暴力，然后有一个想法是，只操作相邻的三个有用。

为啥呢，考虑假设有五个数 a,b,c,d,e，相邻的三个数都没有用同时不相邻的那组有用，也就是 a+c\geqslant 2b,b+d\geqslant 2c,c+e\geqslant 2d,a+e<2c，考虑把第一个和第三个加在一起得到 a+2c+e\geqslant 2(b+d)\geqslant 4c，移项得到 a+e\geqslant 2c 然后就矛盾了，然后归纳一下，只有相邻三个数有用。

然后一直操作最后的形式就会是凸的，因为如果有一个地方不凸我就可以通过操作相邻三个点把他优化掉。

然后考虑这个东西怎么凸，显然就是一点一点取达到差不多直线的位置，然后再做就做不了了。

然后就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[1000005];
int all=0;
int Min=1e16;
int stk1[1000005],top1;
int stk2[1000005],top2;
int stk3[1000005],top3;
int inv(int x,int y){
    x=abs(x),y=abs(y);
    return (x)/y;
}
int mod(int x,int y){
    x=abs(x),y=abs(y);
    return x%y;
}
int getslope(int x,int y){
    return inv(a[x]-a[y],x-y);
}
int getneed(int x,int y){
    return mod(a[x]-a[y],x-y);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        Min=min(Min,a[i]);
    }
    for(int i=1;i<=n;i++){
        if(top1&&a[stk1[top1]]<=a[i])continue;//
        while(top1>1&&getslope(stk1[top1],stk1[top1-1])<getslope(i,stk1[top1])+(!!getneed(i,stk1[top1]))){
            top1--;
        }
        stk1[++top1]=i;
        if(a[i]==Min)break;
    }
    for(int i=n;i>=1;i--){
        if(top2&&a[stk2[top2]]<=a[i])continue;
        while(top2>1&&getslope(stk2[top2],stk2[top2-1])<getslope(i,stk2[top2])+(!!getneed(i,stk2[top2]))){
            top2--;
        }
        stk2[++top2]=i;
        if(a[i]==Min)break;
    }
    for(int i=2;i<=top1;i++){//
        int slope=getslope(stk1[i],stk1[i-1]);
        int need=getneed(stk1[i],stk1[i-1]);
        for(int j=stk1[i-1]+1;j<stk1[i];j++){//
            if(need){
                a[j]=a[j-1]-slope-1;
                need--;
            }
            else{
                a[j]=a[j-1]-slope;
            }
        }
    }
    for(int i=stk1[top1]+1;i<stk2[top2];i++){
        a[i]=a[i-1];
    }
    for(int i=2;i<=top2;i++){
        int slope=getslope(stk2[i],stk2[i-1]);
        int need=getneed(stk2[i],stk2[i-1]);
        for(int j=stk2[i-1]-1;j>stk2[i];j--){//
            if(need){
                a[j]=a[j+1]-slope-1;
                need--;
            }
            else{
                a[j]=a[j+1]-slope;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=a[i];
    }
    printf("%lld\n",ans);
    return 0;
}