首页 > 代码库 > poj 2299 -- Ultra-QuickSort

poj 2299 -- Ultra-QuickSort

2024-07-11 23:48:54   218人阅读

Ultra-QuickSort
Time Limit: 7000MS Memory Limit: 65536K
Total Submissions: 39538 Accepted: 14259

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

59105431230

Sample Output

60
水题，与归并排序求逆序对是一个道理。

 1 /*====================================================================== 2  *           Author :   kevin 3  *         Filename :   Ultra-QuickSort.cpp 4  *       Creat time :   2014-07-14 10:10 5  *      Description : 6 ========================================================================*/ 7 #include <iostream> 8 #include <algorithm> 9 #include <cstdio>10 #include <cstring>11 #include <queue>12 #include <cmath>13 #define clr(a,b) memset(a,b,sizeof(a))14 #define M 50000515 using namespace std;16 long long s[M],temp[M],cnt;17 void mergearray(long long a[],int first,int mid,int last,long long temp[]){18     int i = first,j = mid + 1;19     int m = mid,  n = last;20     int k = 0;21     while(i <= m && j <= n){22         if(a[i] < a[j])23             temp[k++] = a[i++];24         else{25             temp[k++] = a[j++];26             cnt += mid-i+1;27         }28     }29     while(i <= m)30         temp[k++] = a[i++];31     while(j <= n)32         temp[k++] = a[j++];33     for(i = 0; i < k; i++)34         a[first+i] = temp[i];35 }36 void mergesort(long long a[],int first,int last,long long temp[])37 {38     if(first < last){39         int mid = (first + last) / 2;40         mergesort(a,first,mid,temp);41         mergesort(a,mid+1,last,temp);42         mergearray(a,first,mid,last,temp);43     }44 }45 int main(int argc,char *argv[])46 {47     int n;48     while(scanf("%d",&n)!=EOF && n){49         cnt = 0;50         for(int i = 0; i < n; i++){51             scanf("%lld",&s[i]);52         }53         mergesort(s,0,n-1,temp);54         printf("%lld\n",cnt);55     }56     return 0;57 }
View Code

 


联系
我们