首页 > 代码库 > P2234 [HNOI2002]营业额统计 (权值线段树)
P2234 [HNOI2002]营业额统计 (权值线段树)
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
可以用splay做
这里写的权值线段树
把点离散化
以权值为下标建立一颗线段树
然后考虑每一个点
我们需要在这个点的前面(也就是在比这个点小的所有点中)找一个最大的
再在这个点的后面(也就是比这个点小的所有点中)找一个最小的
那么把得到的这两个值分别与这个点的值做差，
再取最小值。
这个值就应该是答案
累加
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define MAXN 50010 5 6 using namespace std; 7 8 const int INF=0x7fffffff; 9 10 struct node { 11 int l,r; 12 int mx,mn; 13 }; 14 node t[MAXN<<2]; 15 16 struct data { 17 int ord,x; 18 bool operator < (const data b) const { 19 return x<b.x; 20 } 21 }; 22 data e[MAXN]; 23 24 int n; 25 26 int d[MAXN],a[MAXN]; 27 28 inline void read(int &x) { 29 int f=1;x=0;char c=getchar(); 30 while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();} 31 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();} 32 x=x*f; 33 } 34 35 inline void pushup(int now) { 36 t[now].mx=max(t[now<<1].mx,t[now<<1|1].mx); 37 t[now].mn=min(t[now<<1].mn,t[now<<1|1].mn); 38 } 39 40 void build_tree(int now,int l,int r) { 41 t[now].l=l; 42 t[now].r=r; 43 if(t[now].l==t[now].r) { 44 t[now].mx=-1; 45 t[now].mn=INF-1; 46 return; 47 } 48 int mid=(l+r)>>1; 49 build_tree(now<<1,l,mid); 50 build_tree(now<<1|1,mid+1,r); 51 pushup(now); 52 } 53 54 void modify(int now,int x) { 55 if(t[now].l==t[now].r) { 56 t[now].mn=t[now].l; 57 t[now].mx=t[now].l; 58 return; 59 } 60 int mid=(t[now].l+t[now].r)>>1; 61 if(x<=mid) modify(now<<1,x); 62 if(x>mid) modify(now<<1|1,x); 63 pushup(now); 64 } 65 66 int querymx(int now,int l,int r) { 67 if(l>r) return -1; 68 if(l<=t[now].l&&r>=t[now].r) return t[now].mx; 69 int mid=(t[now].l+t[now].r)>>1; 70 int ret=-2; 71 if(l<=mid) ret=max(ret,querymx(now<<1,l,r)); 72 if(r>mid) ret=max(ret,querymx(now<<1|1,l,r)); 73 return ret; 74 } 75 76 int querymn(int now,int l,int r) { 77 if(l>r) return INF-1; 78 if(l<=t[now].l&&r>=t[now].r) return t[now].mn; 79 int mid=(t[now].l+t[now].r)>>1; 80 int ret=INF; 81 if(l<=mid) ret=min(ret,querymn(now<<1,l,r)); 82 if(r>mid) ret=min(ret,querymn(now<<1|1,l,r)); //这里qeurymn写成qeurymx mdzz 83 return ret; 84 } 85 86 int main() { 87 read(n); 88 for(int i=1;i<=n;i++) { 89 read(a[i]); 90 e[i].ord=i; 91 e[i].x=a[i]; 92 } 93 sort(e+1,e+1+n); 94 int ord=1; 95 d[1]=e[1].x; 96 a[e[1].ord]=ord; 97 for(int i=2;i<=n;i++) { 98 if(e[i].x!=e[i-1].x) ord++; 99 a[e[i].ord]=ord;100 d[ord]=e[i].x;101 }102 build_tree(1,1,ord);103 int ans=d[a[1]];104 modify(1,a[1]);105 for(int i=2;i<=n;i++) {106 int x=querymx(1,1,a[i]-1);107 int y=querymn(1,a[i],n);108 int tmp=INF;109 if(x!=-1) tmp=min(tmp,d[a[i]]-d[x]);110 if(y!=INF-1) tmp=min(tmp,d[y]-d[a[i]]);111 ans+=tmp;112 modify(1,a[i]);113 }114 printf("%d\n",ans);115 return 0;116 }
P2234 [HNOI2002]营业额统计 (权值线段树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。