zcmimi's blog
查看原题

点击跳转

一个数如果两边的数都比它大,那么删掉它是最优的

那么用单调栈维护就可以了

#include<bits/stdc++.h>
const int N=500011;
int n,a[N],b[N],q[N],tp;long long ans;
int min(int x,int y){return x<y?x:y;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        while(tp>=2&&a[i]>=a[q[tp]]&&a[q[tp]]<=a[q[tp-1]])
            ans+=min(a[q[--tp]],a[i]);
        q[++tp]=i;
    }
    for(int i=1;i<=tp;++i)b[i]=a[q[i]];
    std::sort(b+1,b+tp+1);
    for(int i=1;i<=tp-2;++i)ans+=b[i];
    printf("%lld\n",ans);
}
LG CF442C Artem and Array
comment评论
Search
search