NOIP 营业额统计 splay tree 纯模板

2924: 营业额统计

Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit: 389 Accepted:122

Description

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

该天的最小波动值＝ min{ |该天以前某天的营业额－该天的营业额 | ｝

当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。

Input

测试数据多组，每组的第一行为正整数n（1 <= n <= 32767), 表示该公司从成立一直到现在的天数. 接下来的n行每行有一个整数Ai(Ai <= 1000000) ，表示第i天的营业额。处理到EOF为止。

Output

每组数据占一行，每行输出一个整数，每天最小波动值的和。结果小于2^31

Sample Input

Sample Output

Hint

5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

思路:在出现过的数字中，找出与当前数字x差值最小的值的差值。求和。

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<cstring>
  4 #include<cstdlib>
  5 using namespace std;
  6 const int N = 1e5+5;
  7 const int INF = 0x3f3f3f3f;
  8 int pre[N] , key[N],ch[N][2],root,tot1;
  9 int n;
 10 
 11 void NewNode(int &r ,int father,int k)
 12 {
 13     r = ++tot1;/**保存的位置**/
 14     pre[r] = father;
 15     key[r] = k;
 16     ch[r][0] = ch[r][1] = 0;
 17 }
 18 
 19 void Rotate(int x,int kind)
 20 {
 21     int y = pre[x]; // x  的父亲节点
 22     ch[y][!kind] = ch[x][kind]; /**建立x的kind节点和父亲节点的关系**/
 23     pre[ch[x][kind]] = y;
 24 
 25     if(pre[y]) /**建立x节点和x父亲父亲节点的关系**/
 26     {
 27         int k = ch[ pre[y] ] [ 1] == y;
 28         ch[pre[y]][k] = x;
 29     }
 30     pre[x] = pre[y];
 31 
 32     ch[x][kind] = y; /**建立x和y的关系**/
 33     pre[y] = x;
 34 }
 35 //Splay调整，将结点r调整到goal下面
 36 void Splay(int r , int goal )
 37 {
 38     while(pre[r]!=goal)
 39     {
 40         if( pre[pre[r]] == goal ) Rotate(r,ch[pre[r]][0]==r);
 41         else
 42         {
 43             int y = pre[r];
 44             int kind = ch[pre[y]][0] == y;  /**如果是左节点返回1。否则0。取反的kind**/
 45 
 46             if(ch[y][kind] == r)/**r和父亲节点y的位置，和y和其y父亲节点位置不同。**/
 47             { /**采用 Zig-Zag或Zag-Zig操作**/
 48                 Rotate(r,!kind);
 49                 Rotate(r,kind);
 50             }
 51             else/**Zig-Zig或Zag-Zag操作**/
 52             {
 53                 Rotate(y,kind);
 54                 Rotate(r,kind);
 55             }
 56         }
 57     }
 58     if(goal == 0) root = r;
 59 }
 60 
 61 int Insert(int  k)
 62 {
 63     int r = root;
 64     while( ch[r][key[r]<k]!=0)
 65     {
 66         if( key[r] == k)
 67         {
 68             Splay(r,0);
 69             return 0;
 70         }
 71         r = ch[r][key[r]<k];
 72     }
 73     NewNode(ch[r][key[r]<k],r,k);
 74     Splay(ch[r][key[r]<k],0);
 75     return 1;
 76 }
 77 
 78 int get_pre(int x)
 79 {
 80     int temp = ch[x][0];
 81     if(temp == 0) return INF;
 82     while(ch[temp][1])
 83         temp = ch[temp][1];
 84     return key[x] - key[temp];
 85 }
 86 
 87 int get_next(int x)
 88 {
 89     int temp = ch[x][1];
 90     if(temp == 0) return INF;
 91     while(ch[temp][0])
 92         temp = ch[temp][0];
 93     return key[temp] - key[x];
 94 }
 95 int main()
 96 {
 97     int n , x;
 98     while(scanf("%d",&n)>0)
 99     {
100         root = tot1 = 0;
101         int sum = 0;
102         for(int i=1;i<=n;i++)
103         {
104             scanf("%d",&x);
105             if(i==1)
106             {
107                 sum = sum + x;
108                 NewNode(root,0,x);
109                 continue;
110             }
111             if(Insert(x) == 0) continue;
112             int a = get_pre(root);
113             int b = get_next(root);
114             sum=sum+min(a,b);
115         }
116         printf("%d
",sum);
117     }
118     return 0;
119 }