首页 > 代码库 > POJ-2299 Ultra-QuickSort(逆序对个数)

POJ-2299 Ultra-QuickSort(逆序对个数)

2024-08-18 18:13:49   214人阅读

Ultra-QuickSort
Time Limit: 7000MS   Memory Limit: 65536K
Total Submissions: 57461   Accepted: 21231

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

Source

Waterloo local 2005.02.05
 
哼你以为你让我WA我就不发日志了吗QAQ
技术分享

技术分享

 1 #include "bits/stdc++.h"
 2 #define mem(a,b) memset(a,b,sizeof(a))
 3 using namespace std;
 4 typedef long long LL;
 5 const int MAX=500005;
 6 int n;
 7 struct Poi{
 8     int w,p,z;
 9 }cc[MAX];
10 int c[MAX];
11 void add(int x,int y){for (;x<=n;x+=(x&-x)) c[x]+=y;}
12 int search(int x){int an(0);for (;x>0;x-=(x&-x)) an+=c[x];return an;}
13 bool cmp1(Poi x,Poi y){return x.w>y.w;}
14 bool cmp2(Poi x,Poi y){return x.p<y.p;}
15 void init(){
16     int i,j;
17     for (i=1;i<=n;i++){
18         scanf("%d",&cc[i].w);
19         cc[i].p=i;
20     }
21     sort(cc+1,cc+n+1,cmp1);
22     for (i=1;i<=n;i++){
23         cc[i].z=i;
24     }
25     sort(cc+1,cc+n+1,cmp2);
26     mem(c,0);
27 }
28 int main(){
29     freopen ("ultra.in","r",stdin);
30     freopen ("ultra.out","w",stdout);
31     int i,j;
32     int ans;
33     while (scanf("%d",&n),n){
34         init();ans=0;
35         for (i=1;i<=n;i++){
36             ans+=search(cc[i].z-1);
37             add(cc[i].z,1);
38         }
39         printf("%d\n",ans);
40     }
41     return 0;
42 }

 

 

POJ-2299 Ultra-QuickSort(逆序对个数)


联系
我们