洛谷P2234 [HNOI2002]营业额统计

时间:2021-10-06 00:04:31

题目描述

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

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

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

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

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

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

输入输出格式

输入格式:

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

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

输出格式:

洛谷P2234 [HNOI2002]营业额统计

输入输出样例

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

平衡树的裸题

每次在前面找他的前驱

做差相加

我这的这份可能是平衡树里跑的最快的了

 #include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int MAXN=1e6+;
const int mod=;
const int INF=*0x7ffffff;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin))?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 PetNum;
#define root tree[0].ch[1]
struct node
{
int v,fa,ch[],rec;
}tree[MAXN]; int tot,point;
bool ident(int x)
{
return tree[tree[x].fa].ch[]==x?:;
}
void connect(int x,int fa,int how)
{
tree[x].fa=fa;
tree[fa].ch[how]=x;
}
void rotate(int x)
{
int Y=tree[x].fa;
int R=tree[Y].fa;
int Yson=ident(x);
int Rson=ident(Y);
int B=tree[x].ch[Yson^];
connect(B,Y,Yson);
connect(Y,x,Yson^);
connect(x,R,Rson);
}
void splay(int x,int to)
{
to=tree[to].fa;
while(tree[x].fa!=to)
{
if(tree[tree[x].fa].fa==to) rotate(x);
else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);
else rotate(x),rotate(x);
}
}
void newpoint(int x,int fa)
{
tree[++tot].v=x;
tree[tot].fa=fa;
tree[tot].rec=;
}
void insert(int x)
{
point++;
if(tot==){newpoint(x,);root=tot;return ;}
int now=root;
while()
{
if(tree[now].v==x)
{
tree[now].rec++;
splay(now,root);
return ;
}
int nxt=x<tree[now].v?:;
if(!tree[now].ch[nxt])
{
newpoint(x,now);
tree[now].ch[nxt]=tot;
splay(tot,root);
return ;
}
now=tree[now].ch[nxt];
}
}
int lower(int x)
{
int ans=-INF;
int now=root;
while(now)
{
if(tree[now].v<=x) ans=max(ans,tree[now].v);
int nxt=x<tree[now].v?:;
if(tree[now].ch[nxt]==) return ans;
now=tree[now].ch[nxt];
}
return ans;
}
int upper(int x)
{
int ans=INF;
int now=root;
while(now)
{
if(tree[now].v>=x) ans=min(ans,tree[now].v);
int nxt=x<tree[now].v?:;
if(tree[now].ch[nxt]==) return ans;
now=tree[now].ch[nxt];
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int n=read(),ans=read();
n=n-;
insert(<<);
insert(-<<);
insert(ans);
while(n--)
{
int p=read();
int pre=lower(p);
int lat=upper(p);
ans+=min(abs(pre-p),abs(lat-p));
insert(p);
}
printf("%d",ans);
}

洛谷P2234 [HNOI2002]营业额统计的更多相关文章

  1. 洛谷P2234 &lbrack;HNOI2002&rsqb; 营业额统计 &lbrack;splay&rsqb;

    题目传送门 营业额统计 题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况. Tiger拿出了公司的账本,账本上记录了公司成立以来每天 ...

  2. &lbrack;洛谷P2234&rsqb;&lbrack;HNOI2002&rsqb; 营业额统计 - Treap

    Description Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况. Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额. ...

  3. 洛谷 P2234 &lbrack;HNOI2002&rsqb;营业额统计

    题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况. Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额.分析营业情况是 ...

  4. 洛谷P2234 &lbrack;HNOI2002&rsqb;营业额统计(01Tire树)

    题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况. Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额.分析营业情况是 ...

  5. 洛谷—— P2234 &lbrack;HNOI2002&rsqb;营业额统计

    https://www.luogu.org/problem/show?pid=2234 题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业 ...

  6. 洛谷 2234 &lbrack;HNOI2002&rsqb;营业额统计——treap(入门)

    题目:https://www.luogu.org/problemnew/show/P2234 学习了一下 treap 的写法. 学习材料:https://blog.csdn.net/litble/ar ...

  7. 洛谷&period;2234&period;&lbrack;HNOI2002&rsqb;营业额统计&lpar;Splay&rpar;

    题目链接 //模板吧 #include<cstdio> #include<cctype> #include<algorithm> using namespace s ...

  8. SET &vert;&vert; BZOJ 1588&colon; &lbrack;HNOI2002&rsqb;营业额统计 &vert;&vert; Luogu P2234 &lbrack;HNOI2002&rsqb;营业额统计

    题面:P2234 [HNOI2002]营业额统计 题解:随便写写 注意:cmath中abs函数返回的是一个浮点数,在bzoj上会ce 代码: #include<cstdio> #inclu ...

  9. &lbrack;luogu P2234&rsqb; &lbrack;HNOI2002&rsqb;营业额统计

    [luogu P2234] [HNOI2002]营业额统计 题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况. Tiger拿出了公司 ...

随机推荐

  1. 每次新建项目出现appcompat&lowbar;v7 解决方法

    ADT升级版本后每次新建项目出现appcompat_v7 , 解决方案如下 问题生成:

  2. C&num;的多态性

    参考网址:http://www.cnblogs.com/zhangkai2237/archive/2012/12/20/2826734.html 多态的定义:同一操作作用于不同的对象,可以有不同的解释 ...

  3. Effective Java 51 Beware the performance of string concatenation

    Using the string concatenation operator repeatedly to concatenate n strings requires time quadratic ...

  4. 解决&&num;160&semi;&OpenCurlyDoubleQuote;fatal&&num;160&semi;error&&num;160&semi;C1083&colon;&&num;160&semi;”无法打开包括文件

    添加该项目的附加路径 . 1)右键查看该项目的属性 2)点击配置属性——〉  C/C++  ——〉  常规  ——〉 附加包含目录——〉将缺失文件所在目录添加进去

  5. Message&comma;MessageQueue&comma;Looper&comma;Handler详解&plus;实例

    Message,MessageQueue,Looper,Handler详解+实例 原文地址 Android的Handler使用(这篇简单介绍Handler的使用) 一.几个关键概念 1.Message ...

  6. 替换NavigationController里面的返回按钮

    通过navigationController push进来的controller,默认的返回按钮是将本controller pop出去. 但有时候想在pop出去前完成一些自己的一些事情,这时可以自己写 ...

  7. Linux的错误码

    在使用时需要包含头文件 #include <errno.h> merlin@tfAnalysis:~/projects/tfradius$ cat /usr/include/asm-gen ...

  8. New Windows 10 SDK - Toast Notification

    概述 Toast Notification 在 UWP App 中有很重要的作用,能够很大程度上增强 App 和用户之间的沟通,比如运营推广活动.版本更新.提醒类任务提示等等.Toast Notifi ...

  9. AngularJS学习之旅—AngularJS 过滤器&lpar;七&rpar;

    1.AngularJS 过滤器 过滤器可以使用一个管道字符(|)添加到表达式和指令中. AngularJS 过滤器可用于转换数据: 过滤器 描述 currency 格式化数字为货币格式. filter ...

  10. servlet 乱码解决方法

    一. servlet 发送的html 页面中文乱码 解决方法, 1.加入如下代码 response.setCharacterEncoding("UTF-8"); 2.在html页面 ...