hdu 4911 Inversion(归并)

本文主要是介绍hdu 4911 Inversion(归并)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4911 Inversion

题目大意：给定一个序列，有k次机会交换相邻两个位置的数，问说最后序列的逆序对数最少为多少。

解题思路：每交换一次一定可以减少一个逆序对，所以问题转换成如何求逆序对数。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int maxn = 1e5+5;ll k;
int n, s[maxn], t[maxn];ll merge_sort (int l, int r, int* a, int* b) {if (l == r)return 0;int mid = (l + r) / 2;ll ret = merge_sort(l, mid, a, b) + merge_sort(mid+1, r, a, b);int mvl = l, mvr = mid+1, mv = l;while (mvl <= mid || mvr <= r) {if (mvr > r || (mvl <= mid && a[mvl] <= a[mvr])) {b[mv++] = a[mvl++];} else {ret += mid - mvl + 1;b[mv++] = a[mvr++];}}for (int i = l; i <= r; i++)a[i] = b[i];return ret;
}int main () {while (scanf("%d%I64d", &n, &k) == 2) {for (int i = 1; i <= n; i++)scanf("%d", &s[i]);ll ans = merge_sort(1, n, s, t);printf("%I64d\n", max(ans - k, 0LL));}return 0;
}

这篇关于hdu 4911 Inversion(归并)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---