HNOI2002 营业额统计

题目链接

题解

双向链表裸题

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
pair<ll,int> P[100005];
int n,nex[100005],pre[100005],id[100005];
ll a[100005],ans=0;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}	
void init(){
    n=read();
    int i=1;
    while(~scanf("%lld",&a[i]))P[i].first=a[i],P[i].second=i,i++;
    while(i<=n)P[i].first=0,P[i].second=i,a[i++]=0;
    sort(P+1,P+n+1);
    //for(i=1;i<=n;i++)printf("%lld %d\n",P[i].first,P[i].second);
    for(i=1;i<=n;i++)id[i]=P[i].second; 
    pre[id[1]]=nex[id[n]]=0;
    for(i=1;i<n;i++)
        nex[id[i]]=id[i+1],pre[id[i+1]]=id[i];
}
void solve(){
    for(int i=n;i>=2;i--){
        int tp=pre[i],tn=nex[i];
        ll res=INF;
        if(tp)res=min(res,a[i]-a[tp]);
        if(tn)res=min(res,a[tn]-a[i]);
        ans+=res;
        if(tn)pre[tn]=tp;
        if(tp)nex[tp]=tn;
    }
    printf("%lld\n",ans+a[1]);
}
int main(){
    init();
    solve();
    return 0;
}