Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 38258 | Accepted: 13784 |
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
代码：
//离散化+树状数组
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 500000
struct node
{
int val;
int id;
};
node stu[maxn+];
int n;
__int64 cnt;
int bb[maxn+];
int lowbit(int x)
{
return x&(-x);
}
void ope(int x)
{
while(x<=n)
{
bb[x]++;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=;
while(x>)
{
ans+=bb[x];
x-=lowbit(x);
}
return ans;
}
int cmp(const void *a ,const void *b)
{
return (*(node *)a).val -(*(node *)b).val;
}
int main()
{
int i;
while(scanf("%d",&n),n)
{
memset(bb,,sizeof(int)*(n+));
for(i=;i<n;i++)
{
scanf("%d",&stu[i].val);
stu[i].id=i+;
}
qsort(stu,n,sizeof(stu[]),cmp);
cnt=;
for(i=;i<n;i++)
{
cnt+=sum(n)-sum(stu[i].id);
ope(stu[i].id);
}
printf("%I64d\n",cnt);
}
return ;
}
归并排序：
代码：
//归并排序求逆序数
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 500000
int cc[maxn+];
int aa[maxn+];
__int64 cnt;
void merge(int low ,int mid,int hig)
{
int i,j,k;
i=low;
j=mid;
k=;
while(i<mid&&j<hig)
{
if(aa[i]>aa[j])
{
cc[k++]=aa[j++];
cnt+=mid-i;
}
else
cc[k++]=aa[i++];
}
while(i<mid)
cc[k++]=aa[i++];
while(j<hig)
cc[k++]=aa[j++];
for(k=,i=low;i<hig;i++)
aa[i]=cc[k++];
}
void merge_sort(int st,int en)
{
int mid;
if(st+<en)
{
mid=st+(en-st)/;
merge_sort(st,mid);
merge_sort(mid,en);
merge(st,mid,en);
}
}
int main()
{
int n,i;
while(scanf("%d",&n),n)
{
cnt=;
for(i=;i<n;i++)
scanf("%d",aa+i);
merge_sort(,n);
printf("%I64d\n",cnt);
}
return ;
}
非递归归并排序：
代码：
//归并排序求逆序数
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 500000
int cc[maxn+];
int aa[maxn+];
__int64 cnt;
void merge(int low ,int mid,int hig)
{
int i,j,k;
i=low;
j=mid;
k=;
while(i<mid&&j<hig)
{
if(aa[i]>aa[j])
{
cc[k++]=aa[j++];
cnt+=mid-i;
}
else
cc[k++]=aa[i++];
}
while(i<mid)
cc[k++]=aa[i++];
while(j<hig)
cc[k++]=aa[j++];
for(k=,i=low;i<hig;i++)
aa[i]=cc[k++];
}
//void merge_sort(int st,int en)
//{
// int mid;
// if(st+1<en)
// {
// mid=st+(en-st)/2;
// merge_sort(st,mid);
// merge_sort(mid,en);
// merge(st,mid,en);
// }
//}
void merge_sort(int st,int en)
{
int s,t,i;
t=;
while(t<=(en-st))
{
s=t;
t<<=;
i=st;
while(i+t<=en)
{
merge(i,i+s,i+t);
i+=t;
}
if(i+s<en)
merge(i,i+s,en);
}
if(i+s<en)
merge(i,i+s,en);
}
int main()
{
int n,i;
while(scanf("%d",&n),n)
{
cnt=;
for(i=;i<n;i++)
scanf("%d",aa+i);
merge_sort(,n);
printf("%I64d\n",cnt);
}
return ;
}