P2234 [HNOI2002]营业额统计

admin

https://www.luogu.com.cn/problem/P2234

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

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

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

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

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

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

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

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

输出格式

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
输入输出样例
输入 #1复制
6
5
1
2
5
4
6
输出 #1复制
12
说明/提示
结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

admin

此题也是好题，十几年前的好题，可能比你们年纪还大，有多种方法：
1、线段树可以吧，设每天的营业额在线段树数组中的下标为他本身的值
然后每次输入一个数时我们先在这个数的左边的区间查找最大值
再在右边的区间查找最小值
（这意味着我们要找比这个数小的最大值和比这个数大的最小值）
然后比较两者取差的绝对值最小的加到Ans里即可
2、BST可以吧，为了怕退化成一条链，分别试试splay和treap（能不能treap呀）

admin

先来个STL版的，因为是十几年的题目，所以在现在的机器上居然应跑过了。

1. #include<iostream>
   
2. #include<cstring>
   
3. #include<cstdio>
   
4. #include<set>
   
5. #define inf 0x3f3f3f3f3f3f3fll
   
6. using namespace std;
   
7. set<long long> s;
   
8. set<long long>::iterator l,r;
   
9. long long a,res;
   
10. int n,i;
    
11. int main()
    
12. {
    
13.         s.insert(inf);
    
14.         s.insert(-inf);
    
15.         cin>>n>>res;
    
16.         s.insert(res);
    
17.         for(i=2; i<=n; i++)
    
18.                 {
    
19.                         cin>>a;
    
20.                         l=r=s.lower_bound(a);
    
21.                         l--;
    
22.                         if(*r-a < a-*l)res+=*r-a;
    
23.                         else res+=a-*l;
    
24.                         s.insert(a);
    
25.                 }
    
26.         cout<<res;
    
27.         return 0;
    
28. }

复制代码

admin

先来一个基本的BST，不带任何调整的，锻炼下插入和查找，交上去，还得了70分，不错，说明基本功还在，出题人显然也考虑到了。况且只是十几年前的，当时的电脑还没有现在这么快！

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=0x3FFFFFFF;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,cnt,s[2];
   
8. } a[N];
   
9. int n,x,ans,tot,root;
   
10. void BSTPr(int rt)
    
11. {
    
12.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
    
13.         cout<<a[rt].val<<' ';
    
14.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
    
15. }
    
16. void Ins(int & rt,int x)
    
17. {
    
18.         if (rt==0)
    
19.                 {
    
20.                         rt=++tot;
    
21.                         a[rt].val=x;
    
22.                         a[rt].cnt=1;
    
23.                 }
    
24.         else if (a[rt].val==x) a[rt].cnt++; ///其实可以不要
    
25.         else
    
26.                 {
    
27.                         int k=a[rt].val<x;/// k=0 表示左
    
28.                         Ins(a[rt].s[k],x);
    
29.                 }
    
30. }
    
31. int Find(int rt,int x)
    
32. {
    
33.         if (rt==0) return 0;
    
34.         if (a[rt].val==x) return rt;
    
35.         int k=a[rt].val<x; /// k=0表示左子树中去1表示去右子树
    
36.         return Find(a[rt].s[k],x);
    
37. }
    
38. int Pre(int rt, int x)
    
39. {
    
40.         if(rt==0) return 0;
    
41.         if(a[rt].val>=x) return Pre(a[rt].s[0],x);//递归查找左子树
    
42.         else
    
43.                 {
    
44.                         int t=Pre(a[rt].s[1],x);
    
45.                         if (t==0) return rt;
    
46.                         else if (a[t].val<a[rt].val) return rt;//找右子树中是否存在前驱
    
47.                         else return t;
    
48.                 }
    
49. }
    
50. 
    
51. 
    
52. int Suc(int rt, int x)  ///大于x的最小
    
53. {
    
54.         int p=rt, ans=0;
    
55.         while(p>0)
    
56.                 {
    
57.                         if(a[p].val<=x) p=a[p].s[1];
    
58.                         else
    
59.                                 {
    
60.                                         ans=p;
    
61.                                         p=a[p].s[0];
    
62.                                 }
    
63.                 }
    
64.         return ans;
    
65. }
    
66. int main()
    
67. {
    
68.         cin>>n>>x;
    
69.         ans=x,root=1,tot=1,a[1].val=x;
    
70.         int p0,p1,p2,x1,x2;
    
71.         for(int i=2; i<=n; i++)
    
72.                 {
    
73.                         ///BSTPr(root);
    
74.                         cin>>x;
    
75.                         p0=Find(root,x);
    
76.                         if (p0==0)
    
77.                                 {
    
78.                                         p1=Pre(root,x);
    
79.                                         p2=Suc(root,x);
    
80.                                         x1=x2=inf;
    
81.                                         if (p1>0) x1=(x-a[p1].val);
    
82.                                         if (p2>0) x2=(a[p2].val-x);
    
83.                                         ans+=min(x1,x2);
    
84.                                         Ins(root,x);
    
85.                                 }
    
86.                 }
    
87.         cout<<ans;
    
88.         return 0;
    
89. }

复制代码

admin

再锻炼下自己，把查找前驱和后继改一下，前驱包含自己，也就是说找小于等于自己的最大数，

admin

杯水车薪还是过不了，上一个替罪羊看看，其实意义不大

admin

来一发treap，这次使用了splay里面的那种旋转方法。

admin

来一个splay吧，有点大材小用的感觉。