该题应该有很多的解法，想过用二分查找，但是排序操作的复杂度让我们伤不起。这里用Splay来实现是很方便的。首先插入一个点，即第一个点，然后再依次用二叉排序树方式插入当前点，再把该点旋转到根部（这样方便我们找前驱和后继，否则需要中序遍历整棵树来确定），再在存在前驱和后继的情况下寻找前驱和后继。接下来就很好办了。
代码如下：
#include#include #include #include #define L(x) tree[x].ch[0]#define R(x) tree[x].ch[1]#define INF 0x3ffffff#define MAXN 33000using namespace std;int N, seq[MAXN], que[MAXN], front, rt;struct Node{ int v, ch[2], fa; void New(int v, int fa) { this->v = v, this->fa = fa; ch[0] = ch[1] = 0; }}tree[MAXN];void init(){ for (int i = 0; i < MAXN; ++i) { que[i] = i; } rt = que[++front]; tree[rt].New(seq[1], 0);}int insert(int &rt, int &num, int fa) // 引用仅仅为了速度考虑{ if (rt == 0) { // 说明这个节点是待填充的 int x = que[++front]; rt = x; tree[x].New(num, fa); return x; } if (num > tree[rt].v) { return insert(R(rt), num, rt); } else { return insert(L(rt), num, rt); }}void rotate(int x, int f){ int y = tree[x].fa, z = tree[y].fa; tree[y].ch[!f] = tree[x].ch[f]; tree[ tree[y].ch[!f] ].fa = y; tree[x].ch[f] = y; tree[y].fa = x; tree[x].fa = z; if (z) { tree[z].ch[ R(z) == y ] = x; }}void splay(int x, int obj){ int y, z; while (tree[x].fa != obj) { y = tree[x].fa, z = tree[y].fa; if (z == obj) { rotate(x, L(y) == x); } else if (x == L(y) && y == L(z)) { rotate(y, 1), rotate(x, 1); } else if (x == R(y) && y == R(z)) { rotate(y, 0), rotate(x, 0); } else if (x == R(y) && y == L(z)) { rotate(x, 0), rotate(x, 1); } else { rotate(x, 1), rotate(x, 0); } } if (obj == 0) { rt = x; }}int findPre(int rt, int num){ if (R(rt) == 0) { return tree[rt].v; } else { return findPre(R(rt), num); }}int findNext(int rt){ if (L(rt) == 0) { return tree[rt].v; } else { return findNext(L(rt)); }}int main(){ int pos, ans, pre, next, sum; while (scanf("%d", &N) == 1) { sum = 0; for (int i = 1; i <= N; ++i) { scanf("%d", &seq[i]); } init(); if (N >= 1) { sum += seq[1]; } for (int i = 1; i <= N; ++i) { ans = INF; pos = insert(rt, seq[i], tree[rt].fa); splay(pos, 0); // 这个操作会将pos节点变成根节点 if (L(rt)) { pre = findPre(L(rt), seq[i]); ans = abs(seq[i] - pre); } if (R(rt)) { next = findNext(R(rt)); ans = min(abs(next - seq[i]), ans); } sum += ans; } printf("%d\n", sum); } return 0;}