poj2299Ultra-QuickSort(归并求逆序数)

描述

输入

输出

样例输入

5
9
1
0
5
4
3
1
2
3
0

样例输出

6
0

一看就是冒泡，交换一次记录一次就可以了

但是n的范围达到50W，冒泡O(n^2)的复杂度铁定超时（即使有7000ms，其实这是一个陷阱）

直接用快排又不符合题目的要求（相邻元素交换），快排是建立在二分的基础上的，操作次数肯定比在所要求的规则下的交换次数要更少

 

那么该怎么处理？

 

其实这题题目已经给出提示了：Ultra-QuickSort

特殊的快排，能和快排Quicksort相媲美的就是归并排序Mergesort了，O(nlogn)

 

但是用归并排序并不是为了求交换次数，而是为了求序列的逆序数（学过《线代》的同学应该很熟悉了）

一个乱序序列的逆序数= 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数

 

例如例子的

9 1 0 5 4

由于要把它排列为上升序列，上升序列的有序就是  后面的元素比前面的元素大

而对于序列9 1 0 5 4

9后面却有4个比9小的元素，因此9的逆序数为4

1后面只有1个比1小的元素0，因此1的逆序数为1

0后面不存在比他小的元素，因此0的逆序数为0

5后面存在1个比他小的元素4,因此5的逆序数为1

4是序列的最后元素，逆序数为0

 

因此序列9 1 0 5 4的逆序数 t=4+1+0+1+0 = 6 ，恰恰就是冒泡的交换次数

#include<stdio.h>
#include<string.h>long long int cnt;
void merge(int array[],int left,int mid,int right)
{int *temp=new int[right-left+1];int i,j,p;for(i=left,j=mid+1,p=0;i<=mid&&j<=right;p++){if(array[i]<=array[j]) temp[p]=array[i++];else temp[p]=array[j++],cnt+=mid-i+1;//左边的元素比右边的大，因为左面的已经排完了那么左边剩下的没比完的元素和这个右边的元素都构成了逆序对既为mid-i+1！}while(i<=mid) temp[p++]=array[i++];while(j<=right) temp[p++]=array[j++];for(i=left,p=0;i<=right;i++) array[i]=temp[p++];delete temp;
}
void mergesort(int array[],int left,int right)
{if(left==right) return;else{int mid = (left+right)/2;mergesort(array,left,mid);mergesort(array,mid+1,right);merge(array,left,mid,right);}
}
int main()
{int n;int array[500005];int i;while(~scanf("%d",&n),n){cnt=0;for(i =0;i<n;i++)scanf("%d",&array[i]);mergesort(array,0,n-1);printf("%lld\n",cnt);}return 0;
}

 

#include<stdio.h>
long long int sum;
void merge(int array[],int left,int mid,int right)
{int *temp = new int[right-left+1];int i,j,p;i=left;j=mid+1;p=0;while(i<=mid&&j<=right){if(array[i]<=array[j]){temp[p++]=array[i];i++;}else{temp[p++]=array[j];j++;sum+=mid-i+1;}}while(i<=mid)  temp[p++]=array[i++];while(j<=right) temp[p++]=array[j++];for(i=left,p=0;i<=right;i++){array[i]=temp[p++];}delete temp;
}
void mergesort(int array[],int left,int right)
{if(left==right)  return;else{int mid = (left+right)/2;mergesort( array,left,mid);mergesort(array,mid+1,right);merge(array,left,mid,right);}
}
int main()
{int n;int array[500005];while(~scanf("%d",&n),n){sum=0;for(int i=0;i<n;i++)scanf("%d",&array[i]);mergesort(array,0,n-1);printf("%lld\n",sum);}
}