Ultra-QuickSort
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.
查找逆序数
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 49032 | Accepted: 17936 |
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 sequenceUltra-QuickSort produces the output
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查找逆序数
/*
由于本题实际上就是要求逆序对(即满足i<j,a[i]>a[j]的数对)的个数。而我们再回顾一下归并排序的过程:
假设回溯到某一步,后面的两部分已经排好序(就是说当前需要归并的两个部分都是分别有序的),假设这两个序列为
序列a1:2 3 5 9
序列a2:1 4 6 8
此时我们的目的就是要将a1和a2合并为一个序列。
由于在没排序前a2序列一定全部都是在a1序列之后的,当我们比较a2的1与a1的2时,发现1<2按照归并的思想就会先记录下a2的1,而这里实际上就是对冒泡排序的优化,冒泡是将a2的1依次与a1的9,5,3,2交换就需要4次,而归并却只有一次就完成了,要怎么去记录这个4呢,实际上由于1比2小而2后面还有4个数,也就是说那我的结果就必须要+4,也就是记录a1序列找到第一个比a2某一个大的数,他后面还余下的数的个数就是要交换的次数。
同时我们看a2的4时,a1中第一个比它大的数是5,5之后共有两个数,那结果就+2,。依次下去就可以计算出结果。但是由于我们任然没有改变归并排序的过程。所以复杂度还是O(nlogn)
此题有一坑就是结果会超int32,,用__int64*/
/*
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[500050],Arr[500050];
long long int Sort(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
long long ans=0;
while(i<=mid&&j<=high)
{
if(a[i]<=a[j])
Arr[k++]=a[i++];
else
{
Arr[k++]=a[j++];
ans+=j-k;
}
}
while(i<=mid)
{
Arr[k++]=a[i++];
}
while(j<=high)
{
Arr[k++]=a[j++];
}
for(int i=low;i<=high;i++)
{
a[i]=Arr[i];
}
return ans;
}
long long int MergeSort(int low,int high)
{
if(low>=high) //勿漏
return 0;
long long num=0;
int mid=(low+high)/2;
num+=MergeSort(low,mid);
num+=MergeSort(mid+1,high);
num+=Sort(low,mid,high);
return num;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==0)
break;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%I64d\n",MergeSort(0,n-1)); //只有64位才不WA。
// for(int i=0;i<n;i++)
// cout<<a[i];
}
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[500050],Arr[500050];
long long num=0;
long long int Sort(int low,int mid,int high)
{
int i=low,j=mid+1;
int k=low;
while(i<=mid&&j<=high)
{
if(a[i]<=a[j]) //
Arr[k++]=a[i++];
else
{
Arr[k++]=a[j++];
num+=j-k; //逆序数的统计
}
}
while(i<=mid)
{
Arr[k++]=a[i++];
}
while(j<=high)
{
Arr[k++]=a[j++];
}
for(int i=low;i<=high;i++)
{
a[i]=Arr[i];
}
}
long long int MergeSort(int low,int high)
{
if(low>=high) //勿漏
return 0;
int mid=(low+high)/2;
MergeSort(low,mid);
MergeSort(mid+1,high);
Sort(low,mid,high);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==0)
break;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
num=0;
MergeSort(0,n-1);
printf("%I64d\n",num);//只有64位才不WA。
}
}<a target=_blank href="http://poj/searchproblem?field=source&key=Waterloo+local+2005.02.05" style="text-transform: none; text-decoration: none;"></a>
更多推荐
poj2299 查找逆序数 归并
发布评论