【louguP2234】[HNOI2002]营业额统计（链表）

题目链接

离线用链表维护，先按权值排序，建立链表，记录每一天在链表的位置，然后按天数从大到小查询，查询完删除

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=32770;
const int INF=0x7fffffff;

inline int read(){
    int x=0,f=1; char c=getchar();
    while(c<'0'){ if(c=='-') f=-1; c=getchar(); }
    while(c>='0') x=x*10+c-'0',c=getchar();
    return x*f;
}

int n,Ans;

struct NODE{
    int v,id;
} a[MAXN];

inline bool cmp(NODE x,NODE y){
    return x.v<y.v;
}

int pre[MAXN],nxt[MAXN],val[MAXN],pos[MAXN];

inline int Abs(int x){
    return x>0?x:-x;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
        a[i].v=read(),a[i].id=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i){
        pre[i]=i-1;
        nxt[i]=i+1;
        val[i]=a[i].v;
        pos[a[i].id]=i;
    }
    nxt[n]=0;
    for(int i=n;i>=2;--i){
        int p=pos[i];
        int d=INF;
        if(pre[p]) d=min(d,Abs(val[p]-val[pre[p]]));
        if(nxt[p]) d=min(d,Abs(val[p]-val[nxt[p]]));
        nxt[pre[p]]=nxt[p];
        pre[nxt[p]]=pre[p];
        Ans+=d;
    }
    Ans+=val[pos[1]];
    printf("%d\n",Ans);
    return 0;
}