首页 > 代码库 > POJ 2299 Ultra-QuickSort (归并排序)
POJ 2299 Ultra-QuickSort (归并排序)
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 43446 | Accepted: 15822 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Ultra-QuickSort produces the output
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
算法课上讲过这个,正好学习下逆序对的求法。
#include<iostream> #include<stdio.h> #define M 500010 int a[M]; int aux[M]; long long int ans; using namespace std; void merge(int a[],int l,int mid,int h) { for(int k=l;k<=h;++k) aux[k]=a[k]; int i=l; int j=mid+1; for(int k=l;k<=h;++k) { if(i>mid)a[k]=aux[j++]; else if(j>h)a[k]=aux[i++]; else if(aux[i]<aux[j])a[k]=aux[i++]; else { a[k]=aux[j++]; ans+=mid-i+1;//左边的元素比右边的大,那么左边剩下的没比完的元素和这个右边的元素都构成了逆序对! } } } void sort(int a[],int l,int h) { if(l>=h)return ; int mid=l+(h-l)/2; sort(a,l,mid); sort(a,mid+1,h); merge(a,l,mid,h); } int main(int argc, char *argv[]) { //freopen("2299.in","r",stdin); int n; while(scanf("%d",&n)&&n!=0){ ans=0; for(int i=0;i<n;++i) scanf("%d",&a[i]); sort(a,0,n-1); printf("%lld\n",ans); } return 0; }
POJ 2299 Ultra-QuickSort (归并排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。