HNOI 2002 营业额统计-白红宇

HNOI 2002 营业额统计

阅读量：5976 次

发布时间：2019-06-20

本文共 2209 字，大约阅读时间需要 7 分钟。

评测地点：

简单题，splay

题意：

　　按顺序给出一些数，找出距离当前数最近的数的差，将这些差求和即可。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 100005using namespace std;int cnt=1, rt=0;struct Tree{ int key, size, fa, son[2]; void set(int _key, int _size, int _fa) { key=_key; size=_size; fa=_fa; son[0]=son[1]=0; }}T[MAXN];inline void PushUp(int x){ T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+1;}inline void Rotate(int x, int p) //0左旋 1右旋{ int y=T[x].fa; T[y].son[!p]=T[x].son[p]; T[T[x].son[p]].fa=y; T[x].fa=T[y].fa; if(T[x].fa) T[T[x].fa].son[T[T[x].fa].son[1] == y]=x; T[x].son[p]=y; T[y].fa=x; PushUp(y); PushUp(x);}void Splay(int x, int To) //将x节点插入到To的子节点中{ while(T[x].fa != To) { if(T[T[x].fa].fa == To) Rotate(x, T[T[x].fa].son[0] == x); else { int y=T[x].fa, z=T[y].fa; int p=(T[z].son[0] == y); if(T[y].son[p] == x) Rotate(x, !p), Rotate(x, p); //之字旋 else Rotate(y, p), Rotate(x, p); //一字旋 } } if(To == 0) rt=x;}int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处{ int x=rt; while(x && T[x].key != key) x=T[x].son[key > T[x].key]; if(x) Splay(x, 0); return x;}int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处{ int x=T[rt].son[0]; if(!x) return 0; while(T[x].son[1]) x=T[x].son[1]; //Splay(x, 0); return x;}int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处{ int x=T[rt].son[1]; if(!x) return 0; while(T[x].son[0]) x=T[x].son[0]; //Splay(x, 0); return x;}void Insert(int key) //插入key 并且将该节点转移到根处{ if(!rt) T[rt = cnt++].set(key, 1, 0); else { int x=rt, y=0; while(x) { y=x; x=T[x].son[key > T[x].key]; } T[x = cnt++].set(key, 1, y); T[y].son[key > T[y].key]=x; Splay(x, 0); }}int getclose(int key){ if(!rt) return 0; int x=rt, ret=2000000000; while(x) { ret=min(ret, abs(T[x].key-key)); x=T[x].son[key > T[x].key]; } return ret;}int main (){ int n, x, ans, mi; scanf("%d%d", &n, &x); Insert(x); ans=x; while(--n) { if(scanf("%d", &x)==EOF) x=0; ans+=getclose(x); Insert(x); } printf("%d\n", ans); return 0;}