Bubble Sort

题意：

给你一个1~n的排列,问冒泡排序过程中,数字i(1<=i<=n)所到达的最左位置与最右位置的差值的绝对值是多少

题解：

数字i多能到达的最左位置为min(s[i],i)
i为它的初始位置,s[i]为它的最终位置(因为最后是排好序,这个数是多少,就排在哪个位置,故为s[i])
那最右位置呢?
就是判断数i初始时,右边有多少个数比i小,这个就能用树状数组来求解了
循环从右到左,对于数s[i],我们只需判断它右边1~s[i]-1中有几个数即可

树状数组是从1开始，所以输入尽量也从1开始

代码：

#include <bits/stdc++.h> using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; #define PI(A) cout<<(A)<<endl #define SI(N) cin>>(N) #define SII(N,M) cin>>(N)>>(M) #define cle(a,val) memset(a,(val),sizeof(a)) #define rep(i,b) for(int i=0;i<(b);i++) #define Rep(i,a,b) for(int i=(a);i<=(b);i++) #define reRep(i,a,b) for(int i=(a);i>=(b);i--) #define dbg(x) cout <<#x<<" = "<<(x)<<endl #define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl; #define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;} const double EPS= 1e-9 ;/* / C o d i n g S p a c e / */const int MAXN= 100000+ 9 ; int s[MAXN],N,l[MAXN],r[MAXN];//树状数组 范围是[1,n] int bit[MAXN]; //求前i项和 int SUM(int i) {int s=0;while(i>0){s+=bit[i];i-=i&-i;}return s; } //bit[i]+x void ADD(int i,int x) {while(i<=MAXN){bit[i]+=x;i+=i&-i;} }int main() {int o;SI(o);Rep(T,1,o){cle(bit,0);int ma=0;SI(N);Rep(i,1,N) SI(s[i]);Rep(i,1,N) l[s[i]]=min(s[i],i);for (int i=N;i>0;i--){r[s[i]]=i+SUM(s[i]-1);ADD(s[i],1);}cout<<"Case #"<<T<<":";Rep(i,1,N) cout<<" "<<abs(l[i]-r[i]);cout<<endl;}return 0; }

转载于:https://www.cnblogs.com/s1124yy/p/5741411.html

总结

以上是生活随笔为你收集整理的2016 Multi-University Training Contest 4 Bubble Sort(树状数组模板)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。