P2234 [HNOI2002]营业额统计

题目描述

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

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

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

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

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

输入输出格式

输入格式:

输入由文件’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

这道题可以说是一道平衡树的水题,

但是在这里给出一道带权线段树的做法,

首先我们先将所有的点离散化一下,

然后考虑每一个点

我们需要在这个点的前面(也就是在比这个点小的所有点中)找一个最大的

再在这个点的后面(也就是比这个点小的所有点中)找一个最小的

那么把得到的这两个值分别与这个点的值做差,

再取最小值。

这个值就应该是答案

累加即可

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<cstdlib>
  7 #define lli long long int 
  8 #define ls k<<1
  9 #define rs k<<1|1
 10 using namespace std;
 11 const int MAXN=300001;
 12 const int maxn=0x7fffff;
 13 inline void read(int &n)
 14 {
 15     char c='+';int x=0;bool flag=0;
 16     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 17     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 18     flag==1?n=-x:n=x;
 19 }
 20 struct node
 21 {
 22     int  l,r,mx,mn;
 23 }tree[MAXN];
 24 int a[MAXN];
 25 int d[MAXN];
 26 int hh=-1;
 27 int kk=maxn;
 28 struct lisan
 29 {
 30     int pos, va;
 31 }data[MAXN];
 32 inline int comp(const lisan &a,const lisan &b)
 33 {
 34     return a.va<b.va;
 35 }
 36 inline void update(int k)
 37 {
 38     tree[k].mn=min(tree[ls].mn,tree[rs].mn);
 39     tree[k].mx=max(tree[ls].mx,tree[rs].mx);
 40     
 41 }
 42 inline void build(int ll,int rr,int k)
 43 {
 44     tree[k].l=ll;tree[k].r=rr;
 45     if(tree[k].l==tree[k].r)
 46     {
 47         tree[k].mn=maxn;
 48         tree[k].mx=-1;
 49         return ;
 50     }
 51     int mid=(tree[k].l+tree[k].r)>>1;
 52     build(ll,mid,ls);
 53     build(mid+1,rr,rs);
 54     update(k);
 55 }
 56 inline void query_max(int ll,int rr,int k)
 57 {
 58     if(ll<=tree[k].l&&tree[k].r<=rr)
 59     {
 60         if(tree[k].mn!=maxn)
 61         hh=max(hh,tree[k].mx);
 62         return ;
 63     } 
 64     int mid=(tree[k].l+tree[k].r)>>1;
 65     if(ll<=mid)
 66         query_max(ll,rr,ls);
 67     if(rr>mid)
 68         query_max(ll,rr,rs );
 69     update(k);
 70 }
 71 inline void query_min(int ll,int rr,int k)
 72 {
 73     if(ll<=tree[k].l&&tree[k].r<=rr)
 74     {
 75         if(tree[k].mx!=-1)
 76         kk=min(kk,tree[k].mn);
 77         return ;
 78     } 
 79     int mid=(tree[k].l+tree[k].r)>>1;
 80     if(ll<=mid)
 81         query_min(ll,rr,ls);
 82     if(rr>mid)
 83         query_min(ll,rr,rs);
 84     update(k);
 85 }
 86 void change(int k,int pos)
 87 {
 88     if(tree[k].l==tree[k].r)
 89     {
 90         tree[k].mx=tree[k].mn=tree[k].l;
 91         return ;
 92     }
 93     int mid=(tree[k].l+tree[k].r)>>1;
 94     if(pos<=mid)
 95         change(ls,pos);
 96     if(pos>mid)
 97         change(rs,pos);
 98     update(k);
 99 }
100 int main()
101 {
102     //freopen("turnover.in","r",stdin);
103     //freopen("turnover.out","w",stdout);
104     int n;
105     read(n); 
106     for(int i=1;i<=n;i++)
107     {
108         read(a[i]);
109         data[i].pos=i;
110         data[i].va=a[i];
111     }
112     sort(data+1,data+n+1,comp);
113     int tot=1;
114     a[data[1].pos]=tot;
115     d[1]=data[1].va;//离散化 
116     for(int i=2;i<=n;i++)
117     {
118         if(data[i].va!=data[i-1].va)
119             tot++;
120         a[data[i].pos]=tot;
121         d[tot]=data[i].va;
122     }
123     
124     build(1,tot,1);
125     change(1,a[1]);
126     int ans=d[a[1]];
127     for(int i=2;i<=n;i++)
128     {
129         hh=-1;
130         query_max(1,a[i],1);
131         kk=maxn;
132         query_min(a[i],n,1);
133         
134         if(hh!=-1)        hh=abs(d[a[i]]-d[hh]);
135         else    hh=maxn;
136         if(kk!=maxn)    kk=abs(d[kk]-d[a[i]]);
137         else    kk=maxn;
138         
139         int need=min(hh,kk);
140         ans+=need;
141         change(1,a[i]);
142     }
143     printf("%d",ans);
144     return 0;
145 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

原创译文 | 美国禁令后中兴不能再购买高通芯片,美国方面解释原因

转载声明 本文为灯塔大数据原创内容,欢迎个人转载至朋友圈,其他机构转载请在文章开头标注:“转自:灯塔大数据;微信:DTbigdata” 导读:中美贸易战愈演愈烈...

2755
来自专栏域名资讯

域名投资大佬Mike Mann售9枚域名价格达百万

今年下半年,海外大佬Frank Schilling、Mike Mann以及Andrew Rosener都出手了。域名交易价格达上百万元,今天我们...

1960
来自专栏一“技”之长

Bootstrap响应式前端框架笔记十四——媒体对象与列表组

    在移动开发中经常会使用到列表,使用媒体对象可以方便的创建列表中每一行元素,常规的媒体对象实例如下:

771
来自专栏域名资讯

DN榜:域名380.com、CIF.com高价位居一二

在新一期的DN榜中,一枚3数字380.com以32.3万美元(近214万元)的价格位居第一。3字母CIF.com也毫不逊色,以10万美元约66万元的价...

1790
来自专栏黑白安全

美国人网络安全意识调查:佛州最为糟糕

网络安全公司Webroot近日联合Ponemon Institute开展的研究调查发现,佛罗里达州是美国境内在网络安全方面做的最差的州。Ponemon对美国境内...

802
来自专栏域名资讯

乐豆呀获C1轮融资 三拼域名给力十足

众所周知,域名的价值一般对于广大“藏米家”来说,越短越有意义双拼价值一般较高,因此,很多用户对于三拼域名更是尤为钟意,使用keaixue.com的可爱学近期刚...

2220
来自专栏安恒信息

Anonymous前黑客充当FBI线人,带头攻击多国政府网站

据新加坡联合早报网报道,一位知名网络黑客充当美国联邦调查局线人,带头指挥数百次网络袭击,入侵巴西、伊朗、巴基斯坦、叙利亚、土耳其等多国的政府网站。...

2647
来自专栏区块链中本聪

区块链开发 历害了!两字母.COM买到停不下来,戴跃又收购LP.COM

3118
来自专栏域名资讯

宠舍汇三拼域名 获千万融资

北京疆域资本以及星创投基金完成对“宠舍汇”Pre-A轮1000万人民币融资。其官网域名为chongshehui.com。

640
来自专栏ACM算法日常

畅通工程(并查集)- HDU 1232

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道...

751

扫码关注云+社区

领取腾讯云代金券