题意:给出一些数,然后求这串数字的逆序数,也就是从这个状态到升序状态的最小步数。
思路:归并排序,同时累加子问题的逆序数。
http://blog.csdn.net/morgan_xww/article/details/5742926
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[500010]; __int64 ans; int Left[250005] , Right[250005]; void merge(int p , int q , int r) { int n1 , n2; n1 = q - p + 1; n2 = r - q; int i , j , k; for(i = 0 ; i < n1 ; i ++) Left[i] = a[p+i]; Left[n1] = 0xfffffff; for(i = 0 ; i < n2 ; i ++) Right[i] = a[q+1+i]; Right[n2] = 0xfffffff; i = j = 0; for(k = p ; k <= r ; k ++) { if(Left[i]<=Right[j]) { a[k] = Left[i]; i++; } else { a[k] = Right[j]; j++; ans += n1 - i; //统计子问题的逆序数 } } } void mergesort(int p , int r) { int q; if(p < r) { q = (p + r)/2; mergesort(p , q); mergesort(q+1 , r); merge(p , q , r); } } int main() { int n , i; while(~scanf("%d",&n)) { if(n == 0) break; for(i = 0 ; i < n ; i ++) scanf("%d",&a[i]); ans = 0; mergesort(0 , n-1); printf("%I64d\n",ans); } return 0; }