本文主要是介绍HDU - 4911 Inversion，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
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.
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).
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.
A single integer denotes the minimum number of inversions.
Sample Input
3 1 2 2 1 3 0 2 2 1
Sample Output
1 2
题意：求经过最多k次相邻的交换的操作，使得序列的逆序数对最小是多少
思路：线段树和树状数组错了，然后就用归并排序的方法得到当前序列的逆序数对，然后就是想如果想得到最小的话，那么我们每次能的是把大的数放到后面，这样逆序数会减一，然后就能得到答案了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;int a[maxn], b[maxn<<1];
int n, k;
ll ans;void msort(int s, int t) {int mid = (s + t) >> 1;int qb = 1, bn = t-s+1;if (s >= t)return;msort(s, mid);msort(mid+1, t);int i, j;for (i = s, j = mid+1; i <= mid && j <= t; ) {if (a[i] <= a[j]) {b[qb] = a[i];i++;}else {b[qb] = a[j];ans += mid-i+1;j++;}qb++;}while (i <= mid) b[qb++] = a[i++];while (j <= t)b[qb++] = a[j++];for (i = 1, j = s; i < qb; i++, j++)a[j] = b[i];
}int main() {while (scanf("%d%d", &n, &k) != EOF) {ans = 0;for (int i = 1; i <= n; i++)scanf("%d", &a[i]);msort(1, n);cout << max((ll)0, ans-k) << endl;} return 0;
}这篇关于HDU - 4911 Inversion的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
