求给位大神给解题思路：
题目如下
There is a number sequence A1,A2,...,An. Let f(i)=min{|Aj-Ai| ,j<i}. You only need to compute f(1)+f(2)+...+f(n).
Input
The first line is an integer c which shows the number of cases. For each case there is a single line. The first number is n and the next n positive integer is A1 to An. (n<10000, Ai<100000)
Output
For each case print the answer at a single line.
Sample Input
2
3 1 2 3
4 2 3 1 4
Sample Output
2
3
求思路呀求思路，我只有暴力的算法，结果显然就是超时，伤心

用一个数组模拟二叉搜索树

你给个OJ地址我试试

http://acm.hit.
大神加油

帐号发给我下，这个没法注册

已发

同tle了，感觉不应该啊，就是每次找最接近当前数的数，二搜索树时间复杂度算不错了，如果再要优化可以改成平衡树，但是写起来太复杂了，而且题目叫a simple problem，可能有什么简单的方法没想到吧，我再想想

会不会有什么特殊的数学问题之类？

路过..借10可用分!

求解题思路

果然就是平衡树，直接建立平衡树然后判断，期间被提示使用非法函数好多次，结果居然是不允许使用srand()，无语

#include <iostream>
#include <ctime>
#include <cstdlib>
#define MAX 10010

 
using namespace std;

 
typedef struct
{
        int l,r,key,fix;
}node;

 
class treap
{
public:
        node p[MAX];
        int size,root;
        
        void newT()
        {
//            srand(time(0));
                size=-1;
                root=-1;
                for (int i=0; i<MAX; i++)
                        p[i].l=p[i].r=p[i].key=p[i].fix=0;
        }

 
        void rot_l(int &x)
        {
                int y=p[x].r;
                p[x].r=p[y].l;
                p[y].l=x;
                x=y;
        }

 
        void rot_r(int &x)
        {
                int y=p[x].l;
                p[x].l=p[y].r;
                p[y].r=x;
                x=y;
        }

 
        void insert(int &k,int tkey)
        {
                if (k==-1)
                {
                        k=++size;
                        p[k].l=p[k].r=-1;
                        p[k].key=tkey;
                        p[k].fix=rand();
                }
                else
                if (tkey<p[k].key)
                {
                        insert(p[k].l,tkey);
                        if (p[ p[k].l ].fix>p[k].fix)
                                rot_r(k);
                }
                else
                {
                        insert(p[k].r,tkey);
                        if (p[ p[k].r ].fix>p[k].fix)
                                rot_l(k);
                }

 
        }
        
        int find(int x,int tkey)
        {
                int now=1000000;
                while (x!=-1)
                {
                        now=min(now,abs(tkey-p[x].key));
                        if (now==0) break;
                        if (p[x].key>tkey) x=p[x].l; else x=p[x].r;
                }
                return now;
        }
        
};

 
treap T;

 
int main()
{
        int p,n,ans,j;
        cin>>p;
        
        while (p--)
        {
               cin>>n;
               ans=0;
               T.newT();
               
               cin>>j; T.insert(T.root,j);
               for (int i=2; i<=n; i++)
               {
                      cin>>j;
                      ans+=T.find(T.root,j);
                      T.insert(T.root,j);
               }
               cout<<ans<<endl;
        }
        
        return 0;
}