首页 > 代码库 > HDU4911-Inversion
HDU4911-Inversion
题意:根据题目要求交换相邻的两个元素k次,使得最后剩下的逆序对数最少
思路:如果逆序数大于0,存在0 <= i < n使得交换Ai,Ai+1后逆序数减少1,所求答案就为max(inversion - k, 0);
利用归并排序计算逆序对数。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 1000005; int arr[MAXN], b[MAXN]; int n, k; long long cnt; void merge_sort(int * a, int x, int y, int *b) { if (y - x > 1) { int m = x + (y - x) / 2; int p = x, q = m, i = x; merge_sort(a, x, m, b); merge_sort(a, m, y, b); while (p < m || q < y) { if (q >= y || (p < m && a[p] <= a[q])) b[i++] = a[p++]; else { b[i++] = a[q++]; cnt += m - p; } } for (i = x; i < y; i++) a[i] = b[i]; } } int main() { while (scanf("%d%d", &n, &k) != EOF) { for (int i = 0; i < n; i++) scanf("%d", &arr[i]); cnt = 0; merge_sort(arr, 0, n, b); if (cnt - k > 0) cnt -= k; else cnt = 0; cout << cnt << endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。