首页 > > 程序设计 > C/C++ >

洛谷P2234 [HNOI2002]营业额统计

2018-06-17 21:32:05来源：未知阅读 ()

题目描述

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

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

当最小波动值越大时，就说明营业情况越不稳定。

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

第一天的最小波动值为第一天的营业额。

该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。

输入输出格式

输入格式：

输入由文件’turnover.in’读入。

第一行为正整数n（n<=32767），表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数ai(|ai|<=1000000) ，表示第i天公司的营业额，可能存在负数。

输出格式：

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

平衡树的裸题

每次在前面找他的前驱

做差相加

我这的这份可能是平衡树里跑的最快的了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 const int MAXN=1e6+10;
  6 const int mod=1000000;
  7 const int INF=2*0x7ffffff;
  8 inline char nc()
  9 {
 10     static char buf[MAXN],*p1=buf,*p2=buf;
 11     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin))?EOF:*p1++;
 12 }
 13 inline int read()
 14 {
 15     char c=nc();int x=0,f=1;
 16     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
 17     while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
 18     return x*f;
 19 }
 20 int PetNum;
 21 #define root tree[0].ch[1]
 22 struct node
 23 {
 24     int v,fa,ch[2],rec;
 25 }tree[MAXN];
 26 
 27 int tot,point;
 28 bool ident(int x)
 29 {
 30     return tree[tree[x].fa].ch[0]==x?0:1;
 31 }
 32 void connect(int x,int fa,int how)
 33 {
 34     tree[x].fa=fa;
 35     tree[fa].ch[how]=x;
 36 }
 37 void rotate(int x)
 38 {
 39     int Y=tree[x].fa;
 40     int R=tree[Y].fa;
 41     int Yson=ident(x);
 42     int Rson=ident(Y);
 43     int B=tree[x].ch[Yson^1];
 44     connect(B,Y,Yson);
 45     connect(Y,x,Yson^1);
 46     connect(x,R,Rson);
 47 }
 48 void splay(int x,int to)
 49 {
 50     to=tree[to].fa;
 51     while(tree[x].fa!=to)
 52     {
 53         if(tree[tree[x].fa].fa==to) rotate(x);
 54         else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);
 55         else rotate(x),rotate(x);
 56     }
 57 }
 58 void newpoint(int x,int fa)
 59 {
 60     tree[++tot].v=x;
 61     tree[tot].fa=fa;
 62     tree[tot].rec=1;
 63 }
 64 void insert(int x)
 65 {
 66     point++;
 67     if(tot==0){newpoint(x,0);root=tot;return ;}
 68     int now=root;
 69     while(1)
 70     {
 71         if(tree[now].v==x)
 72         {
 73             tree[now].rec++;
 74             splay(now,root);
 75             return ;
 76         }
 77         int nxt=x<tree[now].v?0:1;
 78         if(!tree[now].ch[nxt])
 79         {
 80             newpoint(x,now);
 81             tree[now].ch[nxt]=tot;
 82             splay(tot,root);
 83             return ;
 84         }
 85         now=tree[now].ch[nxt];
 86     }
 87 }
 88 int lower(int x)
 89 {
 90     int ans=-INF;
 91     int now=root;
 92     while(now)
 93     {
 94         if(tree[now].v<=x)   ans=max(ans,tree[now].v);
 95         int nxt=x<tree[now].v?0:1;
 96         if(tree[now].ch[nxt]==0)    return ans;
 97         now=tree[now].ch[nxt];
 98     }
 99     return ans;
100 }
101 int upper(int x)
102 {
103     int ans=INF;
104     int now=root;
105     while(now)
106     {
107         if(tree[now].v>=x)   ans=min(ans,tree[now].v);
108         int nxt=x<tree[now].v?0:1;
109         if(tree[now].ch[nxt]==0)    return ans;
110         now=tree[now].ch[nxt];
111     }
112 }
113 int main()
114 {
115     #ifdef WIN32
116     freopen("a.in","r",stdin);
117     #else
118     #endif
119     int n=read(),ans=read();
120     n=n-1;
121     insert(1<<30);
122     insert(-1<<30);
123     insert(ans);
124     while(n--)
125     {
126         int p=read();
127         int pre=lower(p);
128         int lat=upper(p);
129         ans+=min(abs(pre-p),abs(lat-p));
130         insert(p);
131     }
132     printf("%d",ans);
133 }