poj 2299

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 66949		Accepted: 25081

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

Sample Output

6
0

Source

因为数组里元素比较大,所以需要离散化处理

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string>
 5 #include <string.h>
 6 #include <cstring>
 7 #include <stdio.h>
 8 #define lowbit(x) x&(-x)
 9 
10 using namespace std;
11 const int maxn=5e5+10;
12 typedef long long ll;
13 
14 int n;
15 int a[maxn];
16 ll c[maxn];
17 
18 struct Node{
19     int v;
20     int order;
21 }b[maxn];
22 
23 void add(int x){
24     for(int i=x;i<=n;i+=lowbit(i))
25         c[i]+=1;
26 }
27 
28 int getsum(int x){
29     ll as=0;
30     for(int i=x;i>0;i-=lowbit(i)){
31 
32         as+=c[i];
33     }
34     return as;
35 }
36 bool cmp(const Node&a,const Node&b){
37     return a.v<b.v;
38 }
39 
40 int main(){
41     ios::sync_with_stdio(0);
42     int i,j;
43     while(~scanf("%d",&n)&&n){
44         for(i=1;i<=n;i++){
45             scanf("%d",&b[i].v);
46             b[i].order=i;
47         }
48         sort(b+1,b+n+1,cmp);
49         for(i=1;i<=n;i++){
50             a[b[i].order]=i;
51         }
52         ll  ans=0;
53         memset(c,0,sizeof(c));
54         for(i=1;i<=n;i++){
55             add(a[i]);
56             ans+=(i-getsum(a[i]));
57         }
58         cout<<ans<<endl;
59     }
60     return 0;
61 }

相关推荐