hdu4911 Inversion --- 归并排序（求逆序对）

题目大意：
输入一个序列{a1,a2,...,an}，交换任意两个相邻元素，不超过k次。在交换之后，问最少的逆序对有多少个？
序列中的一个逆序对是指存在两个数ai和aj，有ai > aj 且1 <=i < j <= n。也就是说，大的数排在小的数前面。

输入：
第一行是n和k，1 <= n <= 10^5，0 <= k <= 10^9；第二行包括n个整数{a1,a2,...,an}，0 <= ai <= 10^9.

输出：
最少的逆序对数量。

输入样例：
3 1
2 2 1

输出样例：
1

 

 

---

 

解题代码---归并排序（求逆序对）

#include <cstdio>
using namespace std;
const int maxn = 100010;
typedef long long ll;
ll a[maxn], b[maxn], cnt; //b[]用于临时存储

/*Mergesort()和Merge()是归并排序*/ 

/*合并操作*/ 
/*合并两个有序的子序列，两个子序列分别是：[l, mid] 和 [mid+1, r]*/
void Merge(ll l, ll mid, ll r) { 
	ll i = l, j = mid + 1, t = 0;
	while (i <= mid && j <= r) {
		if (a[i] > a[j]) {
			b[t++] = a[j++];
			cnt += (mid - i + 1); //记录逆序对数量
		} 
		else b[t++] = a[i++];
	}
	
	/*一个子序列中的数都处理完了，另一个子序列还没有，把剩下的直接复制过来*/
	while (i <= mid) b[t++] = a[i++];
	while (j <= r) b[t++] = a[j++];
	for(i = 0; i < t; i++) a[l + i] = b[i]; //把排好序的b[]复制回a[]
}

void Mergesort(ll l, ll r) {
	if (l < r) {
		ll mid = (l + r) >> 1;
		Mergesort(l, mid);
		Mergesort(mid+1, r);
		Merge(l, mid, r); //合并
	}
}

int main()
{
	ll n, k;
	while (~scanf("%lld %lld",&n,&k)) { //当读完后scanf()返回EOF(-1,二进制表示下各位都是1) 
		cnt = 0;
		for(ll i = 0; i < n; i++) scanf("%d",&a[i]);
		Mergesort(0, n-1); //归并排序
		//cnt<=k，总逆序数不够交换k次或者刚好交换k次，所以进行k次交换后，最少的逆序对数量为0 
		if (cnt <= k) printf("0\n"); 
		else printf("%lld\n",cnt-k); //cnt>k，让k次交换都发生在逆序的相邻数上，那么剩余的逆序对还有cnt-k对 
	}
	
	return 0;
}