题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1588
使用双向链表!
离线做,先抽出来排个序,按排序确定每个位置的 pre 和 nxt ,然后倒序查找,找完一个就删除一个值,更改 pre 和 nxt。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=33000;
int n,pre[maxn],nxt[maxn],rk[maxn];
ll a[maxn],inf=1e12,ans;
bool cmp(int x,int y){return a[x]<a[y];}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),rk[i]=i;
sort(rk+1,rk+n+1,cmp);
for(int i=1;i<=n;i++)
{
pre[rk[i]]=rk[i-1];
nxt[rk[i]]=rk[i+1];
}
for(int i=n;i>1;i--)
{
ll l=inf,r=inf;
if(pre[i])l=abs(a[i]-a[pre[i]]);
if(nxt[i])r=abs(a[i]-a[nxt[i]]);
ans+=min(l,r);
nxt[pre[i]]=nxt[i];
pre[nxt[i]]=pre[i];
}
ans+=a[1];
printf("%lld",ans);
return 0;
}