首页 > 代码库 > 2299 Ultra-QuickSort(归并排序)
2299 Ultra-QuickSort(归并排序)
归并排序第一次做,翻书看了一下归并的思路看了一下别人的博客。
http://poj.org/problem?id=2299
#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
2299 Ultra-QuickSort(归并排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。