0167-Bubble Sort
考え方
普通に指示通りに実装すれば答えを求めることが出来る。
が、それでは面白くないので蟻本を参考にBITを用いて書いてみた。(3/24追加)
実装(C++)
#include <algorithm> #include <vector> #include <cstdio> using namespace std; struct BIT{ private: vector<int> bit;int size; public: BIT(int n){ size=n;bit=vector<int>(n+1); } //i番目の要素にxを加算する void add(int i,int x){ i+=1; while(i<=size)bit[i]+=x,i+=i&-i; } int sum(int i){ i+=1;int s=0; while(i>0)s+=bit[i],i-=i&-i; return s; } }; int main(){ for(int n;scanf("%d",&n),n;){ int a[n],b[n],ans=0; BIT bit(n); for(int i=0;i<n;i++)scanf("%d",a+i),b[i]=a[i]; std::sort(b,b+n); for(int i=0;i<n;i++)a[i]=lower_bound(b,b+n,a[i])-b; for(int i=0;i<n;i++){ ans+=i-bit.sum(a[i]); bit.add(a[i],1); } printf("%d\n",ans); } return 0; }