首页 > 代码库 > HDU - 4911 Inversion

HDU - 4911 Inversion

2024-07-15 23:56:05   221人阅读


Problem Description
bobo has a sequence a1,a2,…,an. He is allowed to swap twoadjacent 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 ai>aj.
 

Input
The input consists of several tests. For each tests:

The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
 

Output
For each tests:

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;
}


联系
我们