题目大意

输入N个数,求每一个数与之前那些数中的最小差的总和。不懂就算了。

大概思路

依题意建立一个二叉搜索树,一个一个的插入,然后求插入节点的前驱和后继,比较其差值取较小者即可。

解题过程

花了一个小时,艰辛地写出Splay,看到前驱后继,果断偷懒用中序遍历来求,简单粗暴TLE...
后来学到了一个好方法,对于Splay,先将所求点Splay到根节点,然后根的左儿子的最右就是其前驱,右儿子的最左就是其后继。
嗯...前者要O(n),后者貌似只要O(logn)。

附个代码,虽然没人会看:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 100005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, a[MAXN];
long long Ans;
struct Splay_Tree {
    int fa[MAXN], key[MAXN], ch[MAXN][2];
    int Index, root;
    
    void Init() { Index = root = -1; }
    
    void Newnode(int p, int x, int f) {
        fa[p] = f; key[p] = x;
        ch[p][0] = ch[p][1] = -1;
    }
    
    void rotate(int p, int d) {
        int f = fa[p]; fa[p] = fa[f];
        ch[f][d] = ch[p][d^1]; fa[ch[p][d^1]] = f;
        ch[p][d^1] = f; fa[f] = p;
        if(fa[p] < 0) root = p;
        else {
            if(ch[fa[p]][0] == f) ch[fa[p]][0] = p;
            else ch[fa[p]][1] = p;
        }
    }
    
    void Splay(int p, const int end_fa) {
        while(fa[p] != end_fa) {
            if(fa[fa[p]] == end_fa) {
                if(p == ch[fa[p]][0]) rotate(p, 0);
                else rotate(p, 1);
            }
            else {
                if((ch[fa[p]][0]==p) ^ (ch[fa[fa[p]]][0]==fa[p])) {
                    for(int i=1; i<=2; i++) {
                        if(p == ch[fa[p]][0]) rotate(p, 0);
                        else rotate(p, 1);
                    }
                }
                else {
                    if(fa[p] == ch[fa[fa[p]]][0]) rotate(fa[p], 0);
                    else rotate(fa[p], 1);
                    if(p == ch[fa[p]][0]) rotate(p, 0);
                    else rotate(p, 1);
                }
            }
        }
    }
    
    void Insert(int x) {
        if(root < 0) {
            Index = root = 0;
            Newnode(root, x, -1);
            return;
        }
        int p = root, f;
        while(p >= 0) {
            f = p;
            if(x <= key[p]) p = ch[p][0];
            else p = ch[p][1];
        }
        int d; if(x<=key[f]) d=0; else d=1;
        ch[f][d] = ++Index;
        Newnode(ch[f][d], x, f);
        Splay(ch[f][d], fa[root]);
    }
    
    int  Query_pre(int p) {
        Splay(p, fa[root]);
        if(ch[p][0] < 0) return -1000000000;
        else p = ch[p][0];
        while(ch[p][1] >= 0) p = ch[p][1];
        return key[p];
    }
    
    int  Query_suf(int p) {
        Splay(p, fa[root]);
        if(ch[p][1] < 0) return 1000000000;
        else p = ch[p][1];
        while(ch[p][0] >= 0) p = ch[p][0];
        return key[p];
    }
    
    void DEBUG() {
        for(int i=0; i<=Index; i++) {
            printf("#    %d : \n", i);
            printf("    fa = %d\n", fa[i]);
            printf("    key = %d\n", key[i]);
            printf("    lc = %d, rc = %d\n", ch[i][0], ch[i][1]);
        }
        puts("========================================");
    }
    
} T;

int main() {

    n = read();
    for(int i=1; i<=n; i++) a[i] = read();
    T.Init(); T.Insert(a[1]);
    Ans = 0;
    for(int i=2; i<=n; i++) {
        T.Insert(a[i]);
        int pre = T.Query_pre(T.Index);
        int suf = T.Query_suf(T.Index);
        Ans += min(a[i]-pre, suf-a[i]);
    }
    printf("%lld\n", Ans+a[1]);
    
    return 0;
}
//代码更新与2016.11.26