博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[HNOI2002]营业额统计 (Splay)
阅读量:4841 次
发布时间:2019-06-11

本文共 2524 字,大约阅读时间需要 8 分钟。

好久没打过数据结构了哈... 把这道题作为splay 的复习题吧,也是个板子.

题目描述

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

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

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

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

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

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

输入输出格式

输入格式:

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

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

输出格式:

输入输出样例

输入样例#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

Solution

太久没打过了,就对着题解一顿打和理解,题意就是找前驱和后继里面和自己差的比较小的差值.

唉,我太菜了...

#include
using namespace std;const int maxn=40008;struct sj{ int fa; int lc; int rc; int data;}tree[maxn];int n,sum,root,flag;void zig(int x) { int y=tree[x].fa; int z=tree[y].fa; tree[y].lc=tree[x].rc; if(tree[x].rc) tree[tree[x].rc].fa=y; tree[x].fa=z; if(z) { if(tree[z].lc==y) tree[z].lc=x; else tree[z].rc=x; } tree[x].rc=y; tree[y].fa=x;}void zag(int x) { int y=tree[x].fa; int z=tree[y].fa; tree[y].rc=tree[x].lc; if(tree[x].lc) tree[tree[x].lc].fa=y; tree[x].fa=z; if(z) { if(tree[z].lc==y) tree[z].lc=x; else tree[z].rc=x; } tree[x].lc=y; tree[y].fa=x;}inline void splay(int x) //将 x 这个点翻到 根的函数.{ while(tree[x].fa)//直到把x旋到根 { int y=tree[x].fa; int z=tree[y].fa; if(!z) //如果到了根的下一位. { if(tree[y].lc==x) zig(x); else zag(x); } else //到最后面即将翻到根的时候需要分类讨论. //zig-zig,zag-zag,zig-zag,zag-zig; { if(tree[y].lc==x&&tree[z].lc==y) zig(y),zig(x); //同为两遍右,即为 zig-zig. if(tree[y].rc==x&&tree[z].rc==y) zag(y),zag(x); //此种为 zag-zag. if(tree[y].rc==x&&tree[z].lc==y) zag(x),zig(x); //zag-zig; if(tree[y].lc==x&&tree[z].rc==y) zig(x),zag(x); //zig-zag; } } root=x; //最后面更新根.}void build(int x,int rt)//x为要插入的节点,rt为当前的节点.{ if(tree[x].data==tree[rt].data) { splay(rt); flag=1; return; } if(tree[x].data
>n; cin>>tree[1].data; root=1;sum+=tree[1].data; for(int i=2;i<=n;i++) { cin>>tree[i].data; insert(i); } cout<
<

转载于:https://www.cnblogs.com/Kv-Stalin/p/9118527.html

你可能感兴趣的文章
巧用「打印」功能实现PDF单页提取
查看>>
【转】Mongo初体验
查看>>
Java中synchronized和同步方法
查看>>
C语言学习记录_2019.01.29
查看>>
个人简历
查看>>
7 Sentences You Shouldn't Say to Your Boss - EVER
查看>>
TurtleBot3-基础例程
查看>>
动态规划之矩阵链
查看>>
Chrome 中的 JavaScript 断点设置和调试技巧 (转载)
查看>>
在Linux shell脚本中root切换到普通用户执行脚本或命令的方法
查看>>
rem,em,px
查看>>
《TCP/IP 详解 卷1:协议》第 10 章:用户数据报协议
查看>>
前端学数据库之基础操作
查看>>
python模块pymysql
查看>>
DAY-9 Linux基础及常用命令(5)
查看>>
unittest-mock-from-import
查看>>
node入门学习(二)
查看>>
通过js禁止输入空格(试用场景:当用字符串拼接插入dom节点时,onkeyup这些方法都不好使可用这个)...
查看>>
Codeforces Edu Round 48 A-D
查看>>
C++cctype软件包函数摆脱,ASCII码!
查看>>