本文主要是介绍poj2299解题报告（归并排序求逆序数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 2299，题目链接http://poj.org/problem?id=2299
题意：
给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。
思路：
其实就是求逆序数，那么直接向到的就是冒泡了，交换一次，记录一次即可。但是n的范围达到50W，冒泡O(n^2)的复杂度铁定超时。
然后、、、发现曾经微软有一道笔试题类似就是求逆序数的，对，没错，用归并。
例：合并两个序列（1,3,5）（2,4,6），新序列第二个元素是2，那么它和它前面的3、5形成了逆序数对，所以....
代码：
//3880K 391MS
#include <cstdio>
#include <algorithm>
int buf[500000];
int ret[500000];
unsigned long long count;
void mergeArray(int *a, int first, int mid, int last, int *ret)
{
int i = first, j = mid+1, k =0;
int m = mid, n = last;
while(i<=m && j<=n){
if (a[i] <= a[j]) {
ret[k++] = a[i++];
}
else {
ret[k++] = a[j++];
count += m-i+1; //记录
}
}
while(i<=m) ret[k++] = a[i++];
while(j<=n) ret[k++] = a[j++];
for (int i=0;i<k; ++i) a[first+i] = ret[i];
}
void mergeSort(int data[], int first, int end, int *ret)
{
if (first < end)
{
int mid = (first + end)/2;
mergeSort(data, first, mid, ret);
mergeSort(data, mid+1, end, ret);
mergeArray(data, first, mid, end, ret);
}
}
int main()
{
int num;
while (true)
{
scanf("%d", &num);
if (num <= 0) break;
for (int i=0; i<num; ++i) scanf("%d", &buf[i]);
count = 0;
mergeSort(buf, 0, num-1, ret);
printf("%lld\n", count);
}
return 0;
}
这篇关于poj2299解题报告（归并排序求逆序数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
