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
题意:给出一串数,求出使用快排变成从小到大排序的最小交换次数。
题解:根据快排加找规律,可以看出就是求这一串数的逆序数,然后就用树状数组写了。因为数据规模大,需要离散化一下,就是去重,重复的数用相同的数表示,所以需要排序。具体看代码。
import java.util.*;
public class Main {
static Scanner cin = new Scanner(System.in);
static int n;
static int [] a;
static int [] c;
static int lowbit(int x) {
return x&(-x);
}
static class Node implements Comparable<Node>{
int val;
int index;
public int compareTo(Node w) {
return this.val-w.val;
}
}//离散化,因为数据大
static int query(int x) { //1-x求和
int sum=0;
while(x!=0) {
sum+=a[x];
x-=lowbit(x);
}
return sum;
}
static void add(int x,int v) {
while(x<=n) {
a[x]+=v;
x+=lowbit(x);
}
}
public static void main(String[] args){
while(cin.hasNext()) {
long sum=0;
n = cin.nextInt();
Node[] node=new Node[n];
if(n==0) break;
a = new int [n+5];
c = new int [n+5];
for (int i = 0; i < n;i++) {
node[i] = new Node();
node[i].val=cin.nextInt();
node[i].index=i+1;
}
Arrays.sort(node);//排序
int id=1;
//Arrays.fill(c,0);
c[node[0].index]=id;
for(int i = 1;i < n;i++){//离散化
if(node[i].val!=node[i-1].val)
c[node[i].index]=++id;
else
c[node[i].index]=id;
}
for(int i = 1;i <= n;i++){
add(c[i],1);//单点更新
sum+=i-query(c[i]);//求 逆序数
}
System.out.println(sum);
}
}
}