POJ 2299 Ultra-QuickSort （归并排序） - c++编程基础

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 sZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcnRlZCBpbiBhc2NlbmRpbmcgb3JkZXIuIEZvciB0aGUgaW5wdXQgc2VxdWVuY2UgPGJyPgo8Y2VudGVyPjkgMSAwIDUgNCAsPC9jZW50ZXI+Cjxicj4KVWx0cmEtUXVpY2tTb3J0IHByb2R1Y2VzIHRoZSBvdXRwdXQgPGJyPgo8Y2VudGVyPjAgMSA0IDUgOSAuPC9jZW50ZXI+Cjxicj4KWW91ciB0YXNrIGlzIHRvIGRldGVybWluZSBob3cgbWFueSBzd2FwIG9wZXJhdGlvbnMgVWx0cmEtUXVpY2tTb3J0IG5lZWRzIHRvIHBlcmZvcm0gaW4gb3JkZXIgdG8gc29ydCBhIGdpdmVuIGlucHV0IHNlcXVlbmNlLgo8cCBjbGFzcz0="pst">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

Sample Output

6
0

算法课上讲过这个，正好学习下逆序对的求法。

#include
  
   
#include
   
     #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]
    
     =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