对于当天的营业额，你要找到之前的数和他差的绝对值最小的和。由于这个是不断在插入的，所以用伸展树来维护。
http://www.lydsy.com/JudgeOnline/problem.php?id=1588
照着kuangbin大牛的代码敲下来的。
#include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 99999999 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 100005; int pre[MAXN],key[MAXN],ch[MAXN][2],root,tot; //父亲结点 键值 左右子树 根节点 节点数量 int n; void Newnode(int &rt,int pa,int k) { rt = ++tot; pre[rt] = pa; key[rt] = k; ch[rt][0] = ch[rt][1] = 0;//空 } void Rotate(int x,int kind) { int y = pre[x]; ch[y][!kind] = ch[x][kind]; pre[ch[x][kind]] = y; if(pre[y]){ ch[pre[y]][ch[pre[y]][1]==y] = x; } pre[x] = pre[y]; ch[x][kind] = y; pre[y] = x; } //将结点rt 调整到goal下面 void splay(int rt,int goal) { while(pre[rt] != goal) { if(pre[pre[rt]] == goal) Rotate(rt,ch[pre[rt]][0]==rt); else { int y = pre[rt]; int kind = (ch[pre[y]][0]==y); if(ch[y][kind] == rt){//rt 和 pre[rt]不在同一方向上 Rotate(rt,!kind); //kind=1时，说明rt在y的右边 而y在pre[y]的左边 Rotate(rt,kind); } else { Rotate(y,kind); Rotate(rt,kind); } } } if(goal == 0) root = rt; } int Insert(int k) { int rt = root; while(ch[rt][key[rt]<k]){//如果key[r]<k，表明当前k在右边，不然去左边 if(key[rt] == k){ splay(rt,0); return 0; } rt = ch[rt][key[rt]<k]; } Newnode(ch[rt][key[rt]<k],rt,k); splay(ch[rt][key[rt]<k],0); return 1; } int get_pre(int rt) { int tmp = ch[rt][0]; if(tmp == 0) return INF; while(ch[tmp][1]) { tmp = ch[tmp][1]; } return key[rt] - key[tmp]; } int get_next(int rt) { int tmp = ch[rt][1]; if(tmp == 0) return INF; while(ch[tmp][0]) { tmp = ch[tmp][0]; } return key[tmp] - key[rt]; } int main() { int i,j; while(~scanf("%d",&n)) { root = tot = 0; int ans = 0; for(i=1; i<=n; i++){ int num; if(scanf("%d",&num)==EOF)num = 0; if(i == 1){ ans += num; Newnode(root,0,num); continue; } if(Insert(num) == 0) continue; int a = get_pre(root); int b = get_next(root); //cout<<a<<" "<<b<<endl; ans += min(a,b); } printf("%d ",ans); } }