2299 Ultra-QuickSort（歸并）

合并排序第一次。連環畫看著合并看著別人的博客的想法。

http://poj.org/problem?

id=2299

#include <stdio.h>
#include <stdlib.h>#define MAX 500001int n,a[MAX], t[MAX];
long long int  sum;//歸并
void Merge(int l, int m, int r)
{int p=0;int i=l, j=m+1;while(i<=m && j<=r){if(a[i]>a[j]){t[p++]=a[j++];sum+=m-i+1;}else{t[p++]=a[i++];}}while(i<=m) t[p++]=a[i++];while(j<=r) t[p++]=a[j++];for(i=0; i<p; i++){a[l+i]=t[i];}
}//歸并排序
void MergeSort(int l, int r)
{int m;if(l<r){m=(l+r)/2;MergeSort(l,m);MergeSort(m+1,r);Merge(l,m,r);}
}int main()
{int i;while(1){scanf("%d",&n);if(n == 0)break;sum=0;for(i=0; i<n; i++){scanf("%d",&a[i]);}MergeSort(0, n-1);printf("%lld\n",sum);}return 0;
}

代碼實現參考：http://www.slyar.com/blog/poj-2299-c.html

解題思路參考：http://blog.csdn.net/lyy289065406/article/details/6647346

版權聲明：本文博主原創文章，博客，未經同意不得轉載。