洛谷P2234 [HNOI2002]营业额统计(01Tire树)
2024-10-01 19:01:09
题目描述
Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况:
当最小波动值越大时,就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。
输入输出格式
输入格式:
输入由文件’turnover.in’读入。
第一行为正整数n(n<=32767) ,表示该公司从成立一直到现在的天数,接下来的n行每行有一个整数ai(|ai|<=1000000) ,表示第i天公司的营业额,可能存在负数。
输出格式:
输入输出样例
说明
结果说明:5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
来一发01Trie树
表示懒得写查找前驱和后继的函数了,
就用kth(查找排名为x的数)和rak(查找x的排名)偷了个懒
找前驱的时候就是kth( rak(x) )
后继是kth( rak(x) +1) (注意这里的前驱后继不是严格的,所以允许重复)
时间复杂度可能有点高,不过还是能水过去的
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=1e6+,INF=1e7;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=nc();}
while(c>=''&&c<=''){x=x*+c-'';c=nc();}
return x*f;
}
int ch[MAXN][],num[MAXN],tot=,root=;
inline void insert(int x)
{
x+=INF;
for(int i=,now=root,t; ~i; i--)
{
if( !(ch[now][ t=x>>i & ]) ) ch[now][t]=++tot;
num[ now=ch[now][t] ]+=;
}
}
inline int rak(int x)
{
x+=INF;
int ans=;
for(int i=,now=root,t; ~i ; i--)
{
if( (t=x>>i &) )
ans+=num[ ch[now][] ];
now=ch[now][t];
}
return ans;
}
inline int kth(int x)
{
int ans=;
for(int i=,now=root; ~i ; i--)
{
if( x>num[ ch[now][] ] ) ans|=<<i,x-=num[ ch[now][] ],now=ch[now][];
else now=ch[now][];
}
return ans-INF;
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int n=read(),ans=read();n=n-;
insert(ans);
while(n--)
{
int x=read();
int pre=kth( rak(x) );
int lat=kth( rak(x) +);
ans+=min( abs(pre-x) ,abs(lat-x) );
insert(x);
}
printf("%d",ans);
}
最新文章
- Entity Framework 代码先行
- Redis总结(四)Redis 的持久化
- block、inline、inline-block
- openwrt编译环境搭建
- 用css实现云状提示框
- Opencv读取视频一闪而过情况分析
- Oracle—RMAN备份(二)
- 任务栏流量监测工具 NetSpeedMonitor 在Windows 8下的安装使用
- 初学MySQL
- 小程序block标签配合if和else 和 动态修改标题栏
- 打怪升级之路—Security+认证通关攻略(401还是501)
- Lock的lockInterruptibly()方法
- centos7搭建elasticsearch
- 转载:浅析@PathVariable 和 @RequestParam
- jmx - first demo
- 写一个栈,实现出栈、入栈、求最小值,时间复杂度为O(1)
- Application.idle方法
- nginx.conf_2017-11-24
- docker最新版本如何自定义配置文件
- 在Windows下安装MongoDB
热门文章
- MYSQL 更新时间自己主动同步与创建时间默认值共存问题
- [Python] Boolean Or ";Mask"; Index Arrays filter with numpy
- JSunpack-n模拟WireShark拦截文件传输
- Spring官方文档翻译——15.4 处理器映射(Handler mappings)
- Light oj 1138 - Trailing Zeroes (III) 【二分查找好题】【 给出N!末尾有连续的Q个0,让你求最小的N】
- iOS学习9_事件分发&;amp;响应链
- mysql通过DATE_FORMAT将错误数据恢复
- JAVA类库LinkList的基本实现
- 无法往SQL Server Management Studio拖脚本
- ireport 追加新报表