题解
双向链表裸题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
}