poj 2299
最编程
2024-07-09 12:25:30
...
题意:给出一个长度为n的数列,你每一次可以随意交换其中两个数字的位置。问你至少交换几次,才能使得这个数列是个单调递增数列。
思路:逆序数。归并排序求逆序数:
归并排序主要是二路归并排序,采用分治的思想:对于某个数组a[n]排序,先将前半部分排序,再将后半部分排序,最后归并两部分。归并排序是一种稳定的排序方式,且时间复杂度为O(n*log2n)。归并排序还可以求一串数中的逆序数。在归并相邻的两个有序子数组:
XlowXlow+1Xlow+2...Xmid和Ymid+1Y2Y3Y4..Yhigh的过程中,令i=low,j=mid+1,其中:Xi<Xi+1,Yi<Yi+1。若在某此比较a[i]与a[j]时,发现a[i]>a[j],说明a[i]与a[j]是一对逆序数,并且a[i+1],a[i+2],...,a[mid]都是大于等于a[i],说明a[i+1]与a[j],a[i+2]与a[j],...,a[mid]与a[j]都是逆序对。因此,逆序对应该加上mid-i+1。
poj 2299代码如下:
#include <iostream>
const int MAX = 500000;
int a[MAX];
int swap[MAX]; //临时数组
int n; //数组a的长度
__int64 result; //数组a中的逆序数
//归并两个已经有序的段:a[low]—a[mid]和a[mid+1]—a[high],使得a[low]—a[high]有序。
void merge(int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int m = 0;
while(i <= mid && j <= high)
{
if(a[i] <= a[j])
{
swap[m++] = a[i];
i++;
}
else
{
swap[m++] = a[j];
j++;
result += mid - i + 1;
}
}
while(i <= mid)
{
swap[m++] = a[i];
i++;
}
while(j <= mid)
{
swap[m++] = a[j];
j++;
}
for(i = 0; i < m; i++)
a[low + i] = swap[i];
}
//归并排序:对a[low]—a[high]进行归并排序。
void mergeSort(int low, int high)
{
int mid;
if(low < high)
{
mid = (low + high) /2;
mergeSort(low, mid);
mergeSort(mid + 1, high);
merge(low, mid, high);
}
}
int main()
{
int i;
while(true)
{
scanf("%d",&n);
if(n == 0) break;
result = 0;
for(i = 0; i < n; i++)
scanf("%d",a+i);
mergeSort(0, n-1);
printf("%I64d\n",result);
}
return 0;
}
推荐阅读
-
理解并实现KM算法:HDU 2225和POJ 2195问题解析
-
巧妙运用反正切函数——Poj 4227题解
-
模拟电梯乘坐过程的POJ 3863问题解析
-
POJ 3358: 简化无限二进制展开的周期 - 应用费马小定理与分数转二进制表示法
-
poj 2914: 斯托尔-王纳算法求解 最小切割问题 (Minimum Cut using Stoer-Wangner Algorithm)
-
最小割-poj-2914
-
POJ2008 数学几何+递推
-
Prime Path (POJ 3126):简单 BFS + 筛选素数方法解析
-
[POJ2396] 预算(带源汇的可行流量的上下限)
-
POJ2396 Budget