Tag: #hdu4911 #逆序数对
题目（原题目：HDU 4911）
bobo has a sequence a 1,a 2,…,a n. He is allowed to swap two adjacent（相邻） numbers for no more than k times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and a i>a j.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
Output
For each tests:
A single integer denotes the minimum number of inversions.
Sample Input
3 1 2 2 1 3 0 2 2 1Sample Output
1 2
本题的要点是求一个数列的逆序数(对)，我们先来看一下逆序数对的简单定义：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2431中，21，43，41，31是逆序，逆序数是4。
那么该如何求逆序对：
方法如下：
考察每一位，判断从这一位往后有多少小于该位的，结果累加，得到最后结果。
例如，2,4,3,1 先判断2，之后有1是小于2的，结果+1，再判断4，之后3,1都小于4，结果+2，判断3时，结果再+1，最后得到结果4.
很好理解，那么如何使用算法实现：当然，我们可以用两重循环暴力求解，但是显而易见O(x2)的复杂度非常高；更高效的方式有：归并排序、树状数组、线段树。
本文为了迎合课上学习的归并排序，所以选择归并排序算法来解。
归并排序：主要思想是将整个序列分成两部分，分别递归将这两部分排好序之后，再和并为一个有序的序列。
在合并的过程中是将两个相邻并且有序的序列合并成一个有序序列，如以下一个无序列和分成的两个有序序列
Seq： 3 4 5 2 6 8 9
Seq1：3 4 5
Seq2：2 6 8 9
合并成一个有序列:
Seq*：2 3 4 5 6 8 9
对于序列seq1中的某个数a[i],序列seq2中的某个数a[j]，如果a[i]<a[j],没有逆序数，如果a[i]>a[j]，那么逆序数为seq1中a[i]后边元素的个数(包括a[i])，即len1-i；
这样累加每次递归过程的逆序数，在完成整个递归过程之后，最后的累加和就是逆序的总数。不难理解。
题中还提到只可交换相邻的数字，这里引入一个逆序数定理
逆序数定理，当逆序对数大于0时，若ak<ak+1,那么交换后逆序对数+1，反之-1。
这个其实也不难理解。
完整代码
#include<iostream>
#include<string>
using namespace std;
#define ll long long
ll cnt ;
void Merge(int* A, int p, int q, int r) //根据算法导论改写
{
int n1 = q - p + 1;
int n2 = r - q;
int i, j, k;
int *L = new int[n1 + 1];
int *R = new int[n2 + 1];
for(i= 0;i< n1;i++)
{
L[i] = A[p + i];
}
for(j= 0;j< n2;j++)
{
R[j] = A[q + j + 1];
}
L[n1] = INT_MAX;//书中的哨兵牌，表示正无穷,这里用INT_MAX来代替。
R[n2] = INT_MAX;
for(i= 0,j= 0,k= p;k<= r;k++)
{
if (L[i]<=R[j])
{
A[k]= L[i];
i++;
}
else //L[i]>R[j]出现逆序
{
A[k]= R[j];
j++;
cnt += (n1 - i); //根据逆序数定理添加的代码
}
}
}
void MergeSort(int* A,int p,int r)
{
if(p< r)
{
int q = (p+ r)/2;
MergeSort(A,p,q);
MergeSort(A,q+1,r);
Merge(A,p,q,r);
}
}
int main()
{
/*int n, k, A[1000000];//n<=10^5
while(cin>>n>>k)
{
cnt = 0;
for(int i =0;i < n;i++)
cin>>A[i];
MergeSort(A,0,n-1);
cnt -= k;
if(cnt<0) cnt=0;
cout<<cnt<<endl;
}*/
//cin和cout效率属实差劲
int n,k;
int a[10000000];
while(scanf("%d%d",&n,&k)!=EOF)
{
cnt=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
MergeSort(a,0,n-1);
printf("%lld\n",max((ll)0,cnt-k));
}
}
参考文章：
https://blog.csdn.net/crescent__moon/article/details/38424829
https://www.cnblogs.com/neopenx/p/4465348.html
https://blog.csdn.net/acm_jl/article/details/51147010
