2299 Ultra-QuickSort(归并排序)
归并排序第一次做,翻书看了一下归并的思路看了一下别人的博客。
#include <stdio.h> #include <stdlib.h> #define MAX 500001 int 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
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。