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
这题很简单的样子，就是求冒泡排序的交换次数，but 超时
归并排序，求逆序数，别问我是什么？看着模板写就好
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int s[],temp[];
long long cut;//这里害我WA了一次
void merge_sort(int* A,int x,int y,int* T )
{
if(y-x>)
{
int m=x+(y-x)/;//划分
int p=x,q=m,i=x;
merge_sort(A,x,m,T);//递归求解
merge_sort(A,m,y,T);
while(p<m||q<y)
{
if(q>=y||(p<m&&A[p]<=A[q]))
T[i++]=A[p++];//从左半数组复制到临时空间
else
{
T[i++]=A[q++];//从右半数组复制到临时空间
cut+= (m-p);//统计逆序数
}
}
for(i=x; i<y; i++)
A[i]=T[i];//从辅助数组复制回原数组
}
}
int main()
{
int n,i;
while(scanf("%d",&n)&&n)
{
cut=;
for(i=; i<n; i++)
scanf("%d",&s[i]);
merge_sort(s,,n,temp);
printf("%lld\n",cut);
}
return ;
}
#include<iostream>
using namespace std;
long long cnt;
void merge(int array[],int left,int mid,int right)
{
int* temp=new int[right-left+];
int i,j,p;
for(i=left,j=mid+,p=; i<=mid&&j<=right; p++)
{
if(array[i]<=array[j])temp[p]=array[i++];
else temp[p]=array[j++],cnt+=(mid-i+);
}
while(i<=mid)temp[p++]=array[i++];
while(j<=right)temp[p++]=array[j++];
for(i=left,p=; i<=right; i++)array[i]=temp[p++];
delete temp;
}
void mergesort(int array[],int left,int right)
{
if(left==right)array[left]=array[right];
else
{
int mid=(left+right)/;
mergesort(array,left,mid);
mergesort(array,mid+,right);
merge(array,left,mid,right);
}
}
int main()
{
int n,array[];
while(cin>>n&&n)
{
cnt=;
for(int i=; i<n; i++)
cin>>array[i];
mergesort(array,,n-);
cout<<cnt<<endl;
}
return ;
}
下面这个是网上找的还算好懂得，耗时是我敲得那个的10倍左右
Hint
Huge input and output,scanf and printf are recommended.