http://acm.fzu.edu.cn/problem.php?pid=1492
TLE了很多，以前向別人要了代碼看不懂，今晚重做，一次AC。主要思想是記錄排序后相鄰的元素并及時更新。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct Node
{
int pos,val;
bool operator<(const Node &a) const
{
return val<a.val;
}
}node[100001];
int pos[100001],alloc[100001][2];//pos 原來元素（1-n)在排序后的位置，alloc排序后相鄰元素在原序列的位置
inline int min(int a,int b)
{
return a>b ? b : a;
}
int main()
{
int i,n,res,t1,t2;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&node[i].val);
node[i].pos=i;
}
sort(node+1,node+n+1);
node[0].pos=0,node[0].val=100000000;
node[n+1].pos=n+1,node[n+1].val=100000000;
pos[0]=0,pos[n+1]=n+1;
for(i=1;i<=n;i++)
{
pos[node[i].pos]=i;
alloc[node[i].pos][0]=node[i-1].pos;
alloc[node[i].pos][1]=node[i+1].pos;
}
res=node[pos[n]].val;
for(i=1;i<n;i++)
{
t1=abs(node[pos[i]].val-node[pos[alloc[i][0]]].val);
t2=abs(node[pos[i]].val-node[pos[alloc[i][1]]].val);
res+=min(t1,t2);
alloc[alloc[i][0]][1]=alloc[i][1];
alloc[alloc[i][1]][0]=alloc[i][0];
}
printf("%d\n",res);
}
return 0;
}