Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "The Number of Inversions"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D
数列 A={a0,a1,...an−1} について、ai>aj かつ i
Aizu Online Judge in C++ #ALDS1_5_D : The Number of Inversions
/* Aizu Online Judge in C++ #ALDS1_5_D : The Number of Inversions https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_D 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; #define INF 1000000001 long long ans=0; void merge(int a[],int left,int mid,int right){ int nl=mid-left; int nr=right-mid; int l[nl+1],r[nr+1]; for(int i=0;i<nl;i++){ l[i]=a[left+i]; } for(int i=0;i<nr;i++){ r[i]=a[mid+i]; } l[nl]=r[nr]=INF; int i=0; int j=0; for(int k=left;k<right;k++){ if(l[i]<r[j]){ a[k]=l[i]; i++; }else{ a[k]=r[j]; j++; ans+=(nl-i); } } } void mergeSort(int a[],int left,int right){ if(left+1<right){ int mid=(left+right)/2; mergeSort(a,left,mid); mergeSort(a,mid,right); merge(a,left,mid,right); } } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } mergeSort(a,0,n); cout<<ans<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/