P2234 [HNOI2002]营业额统计
2024-09-14 09:16:35
题目描述
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:
本题Splay板子题。
每次插入一个数,在二叉搜索树遍历的过程中更新下答案,最后累加就好了。
注意每次插入一个数,若该数已经出现过时,也要把该节点旋到根,否则会T一个点(玄学,我也不知道为什么~)。
代码:
/*Code by 520 -- 9.18*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
#define son(x) (x==ch[fa[x]][1])
using namespace std;
const int N=;
int n,ans,tp,op;
int root,ch[N][],fa[N],date[N],cnt; int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-') x=getchar();
if(x=='-') x=getchar(),f=;
while(x>=''&&x<='') a=(a<<)+(a<<)+(x^),x=getchar();
return f?-a:a;
} il void rotate(int x){
int y=fa[x],z=fa[y],b=son(x),c=son(y),a=ch[x][!b];
z?ch[z][c]=x:root=x; fa[x]=z;
if(a) fa[a]=y; ch[y][b]=a;
fa[y]=x,ch[x][!b]=y;
} il void splay(int x,int i){
while(fa[x]!=i){
RE int y=fa[x],z=fa[y];
if(z==i) rotate(x);
else {
if(son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
} void insert(int &rt,int x){
if(!rt) {rt=++cnt,date[rt]=x,op=rt;return;}
if(date[rt]==x) {tp=,op=rt;return;}
if(date[rt]<x) insert(ch[rt][],x),fa[ch[rt][]]=rt,tp=min(tp,x-date[rt]);
else insert(ch[rt][],x),fa[ch[rt][]]=rt,tp=min(tp,date[rt]-x);
} int main(){
n=gi()-;
int x=gi();ans+=x,insert(root,x);
while(n--){
x=gi(),tp=0x7fffffff;
insert(root,x);
splay(op,),root=op;
ans+=tp;
}
cout<<ans;
return ;
}
最新文章
- BZOJ 2039: [2009国家集训队]employ人员雇佣
- Norflash控制器的Verilog建模之一
- 调试SQLSERVER (三)使用Windbg调试SQLSERVER的一些命令
- Java for LeetCode 226 Invert Binary Tree
- GitHub前50名的Objective-C动画相关库
- 【卡西欧Fx-5800p】市场分析 ppt
- mysql 常用知识
- 重构7-Rename(method,class,parameter)
- Windows下IIS以FastCGI模式运行PHP
- 【Xamarin开发 Android 系列 2】VS2015跨平台开发的几种方式
- Facebook IV Winner&#39;s Interview: 1st place, Peter Best (aka fakeplastictrees)
- 转:快乐Node码农的十个习惯
- class创建单击事件
- javascript面向对象基础讲解(工厂模式、构造函数模式、原型模式、混合模式、动态原型模式)
- 解决Chrome动画”卡顿”的办法
- VBA在WORD应用中如何将格式应用于选定内容
- pytorch模型部署在MacOS或者IOS
- Linux 内核中的数据结构:基数树(radix tree)
- JQuery Rest客户端库
- python3 安装使用 fabirc3 模块以及 fab 命令(转)