本文共 3061 字，大约阅读时间需要 10 分钟。
Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
当最小波动值越大时，就说明营业情况越不稳定。
第一行为正整数n(n＜=32767)，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数ai(ai＜=1000000)，表示第i天公司的营业额。
仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
6
12
结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
HNOI 2002
致我的第一个SPlay,Roate(),Splay(),Newnode(),Insert(),get_pre,get_next;
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rep(i,a,b) for(register int i=a;i<=b;i++) 14 #define il inline 15 #define ll long long 16 #define inf 1<<30 17 using namespace std; 18 const int N=32768; 19 int pre[N*4],key[N*4],ch[N*4][2],n,tot,root; 20 int gi(),gl(); 21 void Newnode(int &p,int fa,int k) { 22 p=++tot; 23 pre[p]=fa; 24 key[p]=k; 25 ch[p][1]=ch[p][0]=0; 26 } 27 void Rotate(int x,int kind) { 28 int y=pre[x]; 29 ch[y][!kind]=ch[x][kind];//you can understand it by moni 30 pre[ch[x][kind]]=y; 31 if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;//// 看y是右儿子还是左儿子 32 pre[x]=pre[y]; 33 pre[y]=x; 34 ch[x][kind]=y; 35 36 } 37 void Splay(int r,int goal) { 38 while(pre[r]!=goal) { 39 if(pre[pre[r]]==goal) Rotate(r,ch[pre[r]][0]==r);// 如果左儿子==r就右旋,kind==1 右旋,kind==0 ,左旋. 40 else { 41 int y=pre[r]; 42 int kind= ch[pre[y]][0]==y;// 三个转,先转父亲.// bug 43 if(ch[y][kind]==r) { 44 Rotate(r,!kind); 45 Rotate(r,kind); 46 } 47 else { 48 Rotate(y,kind); 49 Rotate(r,kind); 50 } 51 } 52 } 53 root = r;// 根 54 } 55 int get_pre(int x) { 56 int tmp=ch[x][0]; 57 if(tmp == 0) return inf; 58 while(ch[tmp][1]) tmp=ch[tmp][1]; 59 return key[tmp]; 60 } 61 int get_next(int x) { 62 int tmp=ch[x][1]; 63 if(tmp == 0) return inf; 64 while(ch[tmp][0]) tmp=ch[tmp][0]; 65 return key[tmp]; 66 } 67 int Insert(int k) { 68 while(ch[root][ k > key[root]]) { 69 if(key[root]==k) { 70 Splay(root,0); 71 return 0; 72 } 73 root = ch[root][ k > key[root]]; 74 } 75 Newnode(ch[root][ k > key[root]],root,k); 76 Splay(ch[root][ k > key[root]],0); 77 return 1; 78 } 79 int main() { 80 freopen("turnover.in","r",stdin); 81 freopen("turnover.out","w",stdout); 82 n=gi();int ans=0;register int k; 83 rep(i,1,n) { 84 85 if(scanf("%d",&k)==EOF) k=0; 86 if(i==1) {ans +=k,Newnode(root,0,k);continue;} 87 if(Insert(k)==0) continue; 88 int a=get_pre(root); 89 int b=get_next(root); 90 ans += min(abs(k-a),abs(b-k));// abs 91 } 92 cout< '9')&&ch!='-') ch=getchar();100 if(ch=='-') ch=getchar(),f=-1;101 while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();102 return res*f;103 }
转载于:https://www.cnblogs.com/ypz999/p/6667976.html