首页 > 代码库 > luogu P2234 [HNOI2002]营业额统计
luogu P2234 [HNOI2002]营业额统计
题目描述
Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：
当最小波动值越大时，就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
输入输出格式
输入格式：
输入由文件’turnover.in’读入。
第一行为正整数n（n<=32767） ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数ai(|ai|<=1000000) ，表示第i天公司的营业额，可能存在负数。
输出格式：
输入输出样例
输入样例#1：
6512546
输出样例#1：
12
说明
结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12、
离散化后建立权值线段树，最小差值为其与前边的最边最大值，和后边最小值的差值取min（）
#include<cstdio>#include<algorithm>#include<map>#define N 50010#define inf 0x7fffffffusing namespace std;int n,a[N],d[N];struct Data{ int x,ord;}data[N];bool cmp(Data a,Data b){ return a.x<b.x;}struct node{ int l,r,sum,mx,mn;}t[N<<2];void pushup(int rt){ t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum; t[rt].mx=max(t[rt<<1].mx,t[rt<<1|1].mx); t[rt].mn=min(t[rt<<1].mn,t[rt<<1|1].mn);}void build(int rt,int l,int r){ t[rt].l=l;t[rt].r=r;t[rt].mx=-1;t[rt].mn=inf-1; if(l==r) return; int mid=(l+r)>>1; if(l<=mid) build(rt<<1,l,mid); if(r>mid) build(rt<<1|1,mid+1,r);}void modify(int rt,int pos){ if(t[rt].l==t[rt].r){ t[rt].sum=1; t[rt].mn=t[rt].l; t[rt].mx=t[rt].l; return; } int mid=(t[rt].l+t[rt].r)>>1; if(pos<=mid) modify(rt<<1,pos); if(pos>mid) modify(rt<<1|1,pos); pushup(rt);}int querymx(int rt,int l,int r){ if(r<l) return -1; if(t[rt].sum==0) return -1; if(l<=t[rt].l&&t[rt].r<=r) return t[rt].mx; int mid=(t[rt].l+t[rt].r)>>1,ret=-2; if(l<=mid) ret=max(ret,querymx(rt<<1,l,r)); if(r>mid) ret=max(ret,querymx(rt<<1|1,l,r)); return ret;}int querymn(int rt,int l,int r){ if(r<l) return inf-1; if(t[rt].sum==0) return inf-1; if(l<=t[rt].l&&t[rt].r<=r) return t[rt].mn; int mid=(t[rt].l+t[rt].r)>>1,ret=inf; if(l<=mid) ret=min(ret,querymn(rt<<1,l,r)); if(r>mid) ret=min(ret,querymn(rt<<1|1,l,r)); return ret;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ if(scanf("%d",&a[i])==EOF) a[i]=0; data[i].ord=i;data[i].x=a[i]; } sort(data+1,data+1+n,cmp); int ord=1;d[1]=data[1].x;a[data[1].ord]=ord; for(int i=2;i<=n;i++){ if(data[i].x!=data[i-1].x) ord++; a[data[i].ord]=ord;d[ord]=data[i].x; } build(1,1,ord); int ans=d[a[1]];modify(1,a[1]); for(int i=2;i<=n;i++){ int x=querymx(1,1,a[i]-1),y=querymn(1,a[i],n),tmp=inf; if(x!=-1) tmp=min(tmp,d[a[i]]-d[x]); if(y!=inf-1) tmp=min(tmp,d[y]-d[a[i]]); ans+=tmp; modify(1,a[i]); } printf("%d\n",ans); return 0;}
luogu P2234 [HNOI2002]营业额统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。