题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1588
这道题貌似很多中做法，我先是用multiset交了一发，然后又写了一发splay。
multiset做法，这个其实就是二分了，只是用set来保持加入一个元素时保持有序
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
multiset<int>S;
multiset<int>::iterator it;
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n;
while (~scanf ("%d",&n))
{
int ans = ;
S.clear();
for (int i = ; i < n; i++)
{
int x;
if (scanf ("%d",&x) == EOF)
x = ;
it = S.lower_bound(x);
if (it == S.begin())
ans += abs(*it-x);
else
{
int s1 = *it;
int s2 = *--it;
ans += min(abs(s1 - x),abs(s2 - x));
}
S.insert(x);
}
printf("%d\n",ans);
}
return ;
}
splay
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
template <class T>
inline bool scan_d(T &ret)
{
char c;
int sgn;
if(c=getchar(),c==EOF)
return ;
while(c!='-'&&(c<''||c>''))
c=getchar();
sgn = (c=='-')?-:;
ret =(c=='-')?:(c-'');
while(c=getchar(),c>=''&&c<='')
ret=ret*+(c-'');
ret*=sgn;
return ;
}
const int maxn = 1e5+;
int fa[maxn],son[maxn][],key[maxn],tot,root; void addNode(int &r,int father,int k)
{
r = ++tot;
fa[r] = father;
key[r] = k;
son[r][] = son[r][] = ;
} void Rotate(int r,int kind)
{
int y = fa[r];
son[y][!kind] = son[r][kind];
fa[son[r][kind]] = y;
if (fa[y])
son[fa[y]][son[fa[y]][]==y] = r;
son[r][kind] = y;
fa[r] = fa[y];
fa[y] = r;
}
void splay(int r,int goal)
{
while (fa[r] != goal)
{
if (fa[fa[r]] == goal)
{
Rotate(r,son[fa[r]][] == r);
}
else
{
int y = fa[r];
int kind = (son[fa[y]][] == y);
if (son[y][kind] == r)
{
Rotate(r,!kind);
Rotate(r,kind);
}
else
{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
if (goal == )
root = r;
}
bool Insert(int k)
{
int r = root;
while (son[r][k > key[r]])
{
if (k == key[r])
{
splay(r,);
return false;
}
r = son[r][k>key[r]];
}
addNode(son[r][k>key[r]],r,k);
splay(son[r][k>key[r]],);
return true;
}
int get_pre(int r)
{
int tmp = son[r][];
if (tmp == )
return inf;
while (son[tmp][])
tmp = son[tmp][];
return key[tmp];
}
int get_next(int r)
{
int tmp = son[r][];
if (tmp==)
return inf;
while (son[tmp][])
tmp = son[tmp][];
return key[tmp] ;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n;
while (~scanf ("%d",&n))
{
tot = ;
root = ;
int ans = ;
for (int i = ; i < n; i++)
{
int x;
if (scanf ("%d",&x) == EOF)
x = ;
if (i == )
{
ans += x;
addNode(root,,x);
}
else
{
if (!Insert(x))
continue;
int l = get_pre(root);
int r = get_next(root);
ans += min(abs(x-l),abs(x-r));
//ans += min(l,r);
}
}
printf("%d\n",ans);
}
return ;
}