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
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).
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
#include
#include
#include
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; }
|