网站后台搜索,重要新闻摘抄2022,如何做个购物网站,音乐网站建设方案1588: [HNOI2002]营业额统计 Time Limit: 5 SecMemory Limit: 162 MBDescription 营业额统计 Tiger最近被公司升任为营业部经理#xff0c;他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本#xff0c;账本上记录了公司成立以… 1588: [HNOI2002]营业额统计 Time Limit: 5 SecMemory Limit: 162 MB Description 营业额统计 Tiger最近被公司升任为营业部经理他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日大减价或者是其他情况的时候营业额会出现一定的波动当然一定的波动是能够接受的但是在某些时候营业额突变得很高或是很低这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况 该天的最小波动值 当最小波动值越大时就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 输入输出要求 Input 第一行为正整数 表示该公司从成立一直到现在的天数接下来的n行每行有一个整数(有可能有负数) 表示第i天公司的营业额。 Output 输出文件仅有一个正整数即Sigma(每天最小的波动值) 。结果小于2^31 。 Sample Input 6 5 1 2 5 4 6 Sample Output 12 HINT 结果说明5|1-5||2-1||5-5||4-5||6-5|54101112 此题数据有问题详见讨论版http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid1588 【题解】 用平衡树来维护插入等操作即可。 平衡树第二题 AC 事实证明zigzag分开来写会更快- 1 #includebits/stdc.h2 using namespace std;3 const int N40010;4 int fa[N],ch[N][2],root,k[N],ind1;5 void zig(int x) { 6 int yfa[x],zfa[y]; 7 fa[y]x;8 fa[x]z; 9 ch[y][0]ch[x][1],fa[ch[x][1]]y,ch[x][1]y;
10 if (ych[z][0]) ch[z][0]x;
11 else ch[z][1]x;
12 //size[y]size[ch[y][0]]size[ch[y][1]]1;
13 }
14 void zag(int x) {
15 int yfa[x],zfa[y];
16 fa[y]x,fa[x]z;
17 ch[y][1]ch[x][0],fa[ch[x][0]]y,ch[x][0]y;
18 if (ych[z][0]) ch[z][0]x;
19 else ch[z][1]x;
20 //size[y]size[ch[y][0]]size[ch[y][1]]1;
21 }
22 void splay(int x,int s) {
23 while (fa[x]!s) {
24 int yfa[x],zfa[y];
25 if (zs) {
26 if (xch[y][0]) zig(x);
27 else zag(x);
28 break;
29 }
30 if (ych[z][0]) {
31 if (xch[y][0]) zig(y),zig(x);
32 else zag(x),zig(x);
33 }
34 else {
35 if (xch[y][1]) zag(y),zag(x);
36 else zig(x),zag(x);
37 }
38 }
39 //size[x]size[ch[x][0]]size[ch[x][1]]1;
40 if (s0) rootx;
41 }
42 inline void newnode(int x,int fax,int key) {
43 xind;
44 ch[x][0]ch[x][1]0;
45 fa[x]fax;
46 k[x]key;
47 }
48 inline int search(int w) {
49 int p,xroot;
50 while(x) {
51 px;
52 if(k[x]w) xch[x][0];
53 else xch[x][1];
54 }
55 return p;
56 }
57 inline void ins(int w){
58 if (root0) {
59 newnode(root,0,w);
60 return ;
61 }
62 int isearch(w);
63 if(wk[i]) newnode(ch[i][0],i,w);
64 else newnode(ch[i][1],i,w);
65 splay(ind,0);
66 }
67 inline int pre(int x) {
68 int tmpch[x][0];
69 while(ch[tmp][1]) tmpch[tmp][1];
70 return k[tmp];
71 }
72 inline int suc(int x) {
73 int tmpch[x][1];
74 while(ch[tmp][0]) tmpch[tmp][0];
75 return k[tmp];
76 }
77 int main() {
78 int n,t,ans0;
79 scanf(%d%d,n,t);
80 root1;k[root]t;
81 ch[root][0]ch[root][1]0;
82 fa[root]0;//printf(hhh);
83 anst;ins(2100000);
84 ins(-2100000);
85 for (int i2;in;i) {
86 if(scanf(%d,t)EOF) t0;
87 ins(t);
88 int apre(root),bsuc(root);
89 ansmin(t-a,b-t);
90 }
91 printf(%d\n,ans);
92 return 0;
93 } View Code 转载于:https://www.cnblogs.com/TonyNeal/p/bzoj1588.html
