1588: [HNOI2002]營業額統計 Description 營業額統計 Tiger最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計並分析公司成立以來的營業情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當複雜的工作。由於節假日 ...
1588: [HNOI2002]營業額統計
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 18547 Solved: 7748
[Submit][Status][Discuss]
Description
營業額統計 Tiger最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計並分析公司成立以來的營業情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當複雜的工作。由於節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況： 該天的最小波動值 當最小波動值越大時，就說明營業情況越不穩定。 而分析整個公司的從成立到現在營業情況是否穩定，只需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程式幫助Tiger來計算這一個值。 第一天的最小波動值為第一天的營業額。 輸入輸出要求
Input
第一行為正整數 ，表示該公司從成立一直到現在的天數，接下來的n行每行有一個整數(有可能有負數) ，表示第i 天公司的營業額。 天數n<=32767, 每天的營業額ai <= 1,000,000。 最後結果T<=2^31
Output
輸出文件僅有一個正整數，即Sigma(每天最小的波動值) 。結果小於2^31 。
Sample Input
65
1
2
5
4
6
Sample Output
12HINT
結果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
該題數據bug已修複.----2016.5.15
Source
1 #include<algorithm> 2 #include<cstdio> 3 #include<iostream> 4 #include<cstdlib> 5 #include<cmath> 6 using namespace std; 7 8 const int maxn=32767; 9 typedef long long ll; 10 11 struct node{ 12 int d,n,c,f,son[2];//d?a?μ,f?a???×μ?±ào?,c?a????μ??úμ?êy,n?aí??μμ??úμ???êy 13 }t[41000]; 14 int len,root; 15 16 inline void update(int x)//?üD?x?ù????μ??úμ?êy 17 { 18 int lc=t[x].son[0],rc=t[x].son[1]; 19 t[x].c=t[lc].c+t[rc].c+t[x].n; 20 } 21 22 inline void add(int d,int f)//ìí?ó?μ?adμ?μ?,è?f?a???×,í?ê±,fò2è??ü?ao￠×ó 23 { 24 len++; 25 t[len].d=d; 26 t[len].n=1; 27 t[len].c=1; 28 t[len].f=f; 29 if(d<t[f].d) 30 t[f].son[0]=len; 31 else 32 t[f].son[1]=len; 33 t[len].son[0]=t[len].son[1]=0; 34 } 35 36 inline void rotate(int x,int w)//×óDy(x,0)?ò??óòDy(x,1) 37 { 38 int f=t[x].f,ff=t[f].f;//x?úDy×a???°,òaè·?¨xμ????×foíòˉòˉff 39 //??à′?¨á￠1??μ 40 int r,R;//r′ú±í?ù±2,R±íê???±2 41 //óD4????é?:?òx,?òμ??ù×ó,?òμ????×,?òμ?òˉòˉ 42 r=t[x].son[w];R=f;//xμ??ù×ó->×?±?μ±D??ù×ó 43 t[R].son[1-w]=r; 44 if(r!=0) 45 t[r].f=R; 46 47 r=x;R=ff;//x->×?±?μ±D??ù×ó 48 if(t[R].son[0]==f) 49 t[R].son[0]=r; 50 else 51 t[R].son[1]=r; 52 t[r].f=R; 53 54 r=f;R=x;//xμ????×->×?±?μ±D??ù×ó 55 t[R].son[w]=r; 56 t[r].f=R; 57 58 update(f);//?è?üD?′|óú??2?μ?μ?f 59 update(x);//?ù?üD?é?2?μ?x 60 } 61 62 inline void splay(int x,int rt)//??oˉêy1|?üê??aá?è?x±?3értμ?o￠×ó(×óóò???éò?) 63 { 64 while(t[x].f!=rt)//è?1?xμ?òˉòˉê?rt,???′x??DèòaDy×aò?′?(?àμ±óúì?ò?2?) 65 { 66 int f=t[x].f,ff=t[f].f; 67 if(ff==rt) 68 { 69 if(t[f].son[0]==x) 70 rotate(x,1); 71 else 72 rotate(x,0); 73 } 74 else 75 { 76 if(t[ff].son[0]==f&&t[f].son[0]==x) 77 { 78 rotate(f,1);rotate(x,1); 79 } 80 else if(t[ff].son[1]==f&&t[f].son[1]==x) 81 { 82 rotate(f,0);rotate(x,0); 83 } 84 else if(t[ff].son[0]==f&&t[f].son[1]==x) 85 { 86 rotate(x,0);rotate(x,1); 87 } 88 else if(t[ff].son[1]==f&&t[f].son[0]==x) 89 { 90 rotate(x,1);rotate(x,0); 91 } 92 } 93 } 94 if(rt==0) 95 root=x; 96 } 97 98 inline int findip(int d)//?ò?μ?adμ??úμ?μ??·,213?:è?1?2?′??úd,óD?é?üê??ó?üdμ?(?ò′ó?òD?) 99 { 100 int x=root; 101 while(t[x].d!=d) 102 { 103 if(d<t[x].d) 104 { 105 if(t[x].son[0]==0) 106 break; 107 else 108 x=t[x].son[0]; 109 } 110 else 111 { 112 if(t[x].son[1]==0) 113 break; 114 else 115 x=t[x].son[1]; 116 } 117 } 118 return x; 119 } 120 121 inline void insert(int d)//2?è?êy?μ?adμ?ò????úμ? 122 { 123 if(root==0) 124 { 125 add(d,0); 126 root=len; 127 return ; 128 } 129 int x=findip(d); 130 if(t[x].d==d) 131 { 132 t[x].n++; 133 update(x); 134 splay(x,0); 135 } 136 else 137 { 138 add(d,x); 139 update(x); 140 splay(len,0); 141 } 142 } 143 144 inline void del(int d)//é?3yêy?μ?adμ?ò????úμ? 145 { 146 int x=findip(d); 147 splay(x,0);//?òè?,2￠?òè?yμ±ê÷?ù 148 if(t[x].n>1)//?à??éí·Y,?í2?ó?é?μ? 149 { 150 t[x].n--; 151 update(x); 152 return ; 153 } 154 if(t[x].son[0]==0&&t[x].son[1]==0) 155 { 156 root=0; 157 len=0; 158 return ; 159 } 160 else if(t[x].son[0]==0&&t[x].son[1]!=0) 161 { 162 root=t[x].son[1]; 163 t[root].f=0; 164 } 165 else if(t[x].son[0]!=0&&t[x].son[1]==0) 166 { 167 root=t[x].son[0]; 168 t[root].f=0; 169 } 170 else 171 { 172 int p=t[x].son[0]; 173 while(t[p].son[1]!=0) 174 p=t[p].son[1]; 175 splay(p,x); 176 177 int r=t[x].son[1],R=p; 178 179 t[R].son[1]=r; 180 t[r].f=R; 181 182 root=R; 183 t[root].f=0; 184 update(R); 185 } 186 } 187 188 inline int findrank(int d)//?ò???? 189 { 190 int x=findip(d); 191 splay(x,0); 192 return t[t[x].son[0]].c+1; 193 } 194 195 inline int findshuzhi(int k)//?ò?????akμ??μ 196 { 197 int x=root; 198 while(true) 199 { 200 int lc=t[x].son[0],rc=t[x].son[1]; 201 if(k<=t[lc].c) 202 x=lc;//è￥×óo￠×ó2é?ò 203 else if(k>t[lc].c+t[x].n) 204 { 205 k-=t[lc].c+t[x].n; 206 x=rc; 207 }//è￥óòo￠×ó2é?ò 208 else 209 break;//?íê??? 210 } 211 splay(x,0); 212 return x; 213 } 214 215 inline int findqianqu(int d)//?ò?°?y 216 { 217 int x=findip(d); 218 splay(x,0); 219 if(d<=t[x].d&&t[x].son[0]!=0) 220 { 221 x=t[x].son[0]; 222 while(t[x].son[1]!=0) 223 x=t[x].son[1]; 224 } 225 if(t[x].d>=d)//è?1?ê?if(t[x].d>d)?ò?òμ?μ?ê?:D?óúμèóúdμ??°?y 226 x=0; 227 return x; 228 } 229 230 inline int findhouji(int d)//?òoó?ì 231 { 232 int x=findip(d); 233 splay(x,0); 234 if(t[x].d<=d&&t[x].son[1]!=0) 235 { 236 x=t[x].son[1]; 237 while(t[x].son[0]!=0) 238 x=t[x].son[0]; 239 } 240 if(t[x].d<=d) 241 x=0; 242 return x; 243 } 244 245 int main() 246 { 247 int n; 248 ll ans=0; 249 scanf("%d",&n); 250 len=0; 251 root=0; 252 for(int i=1;i<=n;i++) 253 { 254 int x; 255 scanf("%d",&x); 256 insert(x); 257 if(i==1) 258 { 259 ans+=x; 260 continue; 261 } 262 int qq=findqianqu(x),hj=findhouji(x),id=findip(x); 263 if(t[id].n>1)continue; 264 if(qq==0) 265 { 266 ans+=abs(x-t[hj].d); 267 } 268 else if(hj==0) 269 { 270 ans+=abs(x-t[qq].d); 271 } 272 else 273 { 274 ans+=min(abs(x-t[qq].d),abs(x-t[hj].d)); 275 } 276 } 277 printf("%lld\n",ans); 278 return 0; 279 }
