Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 54883 | Accepted: 20184 |
Description
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
题意：给你长度为n个不同的数，问最少需要交换多少次使得升序 只能交换相邻的两个 其实就是冒泡排序的过程
题解：直接模拟的话会超时 树状数组处理，n只有100000 但是0 ≤ a[i] ≤ 999,999,999
如果开树状数组的话 会炸 所以先离散化一下 只要记录数的相对大小就可以了。求每个数的逆序数对数然后求和输出
逆序对：设A[1..n]是一个包含N个非负整数的数组。如果在i〈 j的情况下，有A〉A[j]，则(i,j)就称为A中的一个逆序对。
还有一种归并排序的写法 再补
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<queue>
#include<cmath>
#define ll __int64
#define PI acos(-1.0)
#define mod 1000000007
using namespace std;
int n;
struct node
{
int v;
int pos;
}N[];
int a[];
int tree[];
bool cmp(struct node aa,struct node bb)
{
return aa.v<bb.v;
}
int lowbit(int t) {return t&(-t);}
void add(int i,int v){
for(;i<=n;i+=lowbit(i))
tree[i]+=v;
}
int sum(int i){//sum 就是统计之前有多少个小于i的数
int ans=;
for(;i>;i-=lowbit(i))
ans+=tree[i];
return ans;
}
int main()
{
while(~scanf("%d",&n)){
if(n==)
break;
for(int i=;i<=n;i++)
{
scanf("%d",&N[i].v);
N[i].pos=i;
}
sort(N+,N++n,cmp);
for(int i=;i<=n;i++)//离散化
a[N[i].pos]=i;
for(int i=;i<=n;i++)//初始化
tree[i]=;
ll ans=;
for(int i=;i<=n;i++)
{
add(a[i],);//注意修改值为1
ans+=(i-sum(a[i]));
}
printf("%I64d\n",ans);
}
return ;
}