三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 洛谷P2234 [HNOI2002]营业额统计(01Tire树) -> 正文阅读
 

[C++]洛谷P2234 [HNOI2002]营业额统计(01Tire树)

洛谷P2234 [HNOI2002]营业额统计(01Tire树) 题目描述
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
来一发01Trie树
表示懒得写查找前驱和后继的函数了,
就用kth(查找排名为x的数)和rak(查找x的排名)偷了个懒
找前驱的时候就是kth( rak(x) )
后继是kth( rak(x) +1) (注意这里的前驱后继不是严格的,所以允许重复)
时间复杂度可能有点高,不过还是能水过去的

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<cstdlib>
 6 #include<cstring>
 7 using namespace std;
 8 const int MAXN=1e6+10,INF=1e7;
 9 inline char nc()
10 {
11     static char buf[MAXN],*p1=buf,*p2=buf;
12     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
13 }
14 inline int read()
15 {
16     char c=nc();int x=0,f=1;
17     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
18     while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
19     return x*f;
20 }
21 int ch[MAXN][2],num[MAXN],tot=2,root=1;
22 inline void insert(int x)
23 {
24     x+=INF;
25     for(int i=31,now=root,t; ~i; i--)
26     {
27         if( !(ch[now][ t=x>>i &1 ]) )    ch[now][t]=++tot;
28         num[ now=ch[now][t] ]+=1;
29     }
30 }
31 inline int rak(int x)
32 {
33     x+=INF;
34     int ans=0;
35     for(int i=31,now=root,t; ~i ; i--)
36     {
37         if( (t=x>>i &1) )    
38             ans+=num[ ch[now][0] ];
39         now=ch[now][t];
40     }
41     return ans;
42 }
43 inline int kth(int x)
44 {
45     int ans=0;
46     for(int i=31,now=root; ~i ; i--)
47     {
48         if( x>num[ ch[now][0] ] )    ans|=1<<i,x-=num[ ch[now][0] ],now=ch[now][1];
49         else now=ch[now][0];
50     }
51     return ans-INF;
52 }
53 int main()
54 {
55     #ifdef WIN32
56     freopen("a.in","r",stdin);
57     #else
58     #endif
59     int n=read(),ans=read();n=n-1;
60     insert(ans);
61     while(n--)
62     {
63         int x=read();
64         int pre=kth( rak(x) );
65         int lat=kth( rak(x) +1);
66         ans+=min( abs(pre-x) ,abs(lat-x) );
67         insert(x);
68     }
69     printf("%d",ans);
70 }

  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
二叉搜索树与双向链表
C++的内存泄漏检测【转载】
C++重载流插入运算符和流提取运算符【转】
统计页码数字0~9分别出现了多少次
上一篇文章           查看所有文章
加:2017-12-02 23:23:46  更:2017-12-02 23:23:53 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年12日历
2017-12-17 18:03:31
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库