P2234 [HNOI2002]营业额统计
2018-06-17 22:09:56来源:未知 阅读 ()
题目描述
Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况:
当最小波动值越大时,就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
输入输出格式
输入格式:
输入由文件’turnover.in’读入。
第一行为正整数n(n<=32767) ,表示该公司从成立一直到现在的天数,接下来的n行每行有一个整数ai(|ai|<=1000000) ,表示第i天公司的营业额,可能存在负数。
输出格式:
输入输出样例
6 5 1 2 5 4 6
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:浮点数的那点事
下一篇:P3376 【模板】网络最大流
- 洛谷P2234 [HNOI2002]营业额统计 2018-06-17
- 洛谷P2234 [HNOI2002]营业额统计(01Tire树) 2018-06-17
- [HNOI2002]-洛谷2234-营业额统计-Treap 2018-06-17
- BZOJ 1588: [HNOI2002]营业额统计 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash