POJ2299 Ultra-QuickSort

发布时间:2017-1-20 13:38:10 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ2299 Ultra-QuickSort",主要涉及到POJ2299 Ultra-QuickSort方面的内容,对于POJ2299 Ultra-QuickSort感兴趣的同学可以参考一下。

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. 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 开始用冒泡儿做,超时。 看到提示逆序对,看来是用归并排序做的时候记录逆序对数。 开始WA不得其解,原来是times需要long long 才放得下。 #include <stdio.h> #include <stdlib.h> #include <vector> #include <time.h> #include <string.h> #include <iostream> using namespace std; vector<__int64> res; int dat[500000]; int tmp[500000]; int n; __int64 times; void merge_sort(int *a,int l,int r){ if(l>=r) return; int mid = (l+r)/2; merge_sort(a,l,mid); merge_sort(a,mid+1,r); int i=l,j=mid+1; int k=0; while(i<=mid && j<=r){ if(a[i]>a[j]){ tmp[k++] = a[j++]; times += mid-i+1; } else tmp[k++] = a[i++]; } while(i<=mid) tmp[k++] = a[i++]; while(j<=r) tmp[k++] = a[j++]; memcpy(a+l,tmp,(r-l+1)*sizeof(int)); } void process(){ times=0; merge_sort(dat,0,n-1); res.push_back(times); } int main(){ while(true){ scanf("%d",&n); if(n==0){ for(int i=0;i<res.size();++i) cout<<res[i]<<endl; //system("pause"); return 0; } int t=n,i=0; while(t--){ scanf("%d",&dat[i++]); } process(); } //system("pause"); return 0; }