描述

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≤ia
j.

输入

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).

输出

For each tests: A single integer denotes the minimum n umber of inversio
ns.

样例输入

3 0
3 2 1

样例输出

3

思路

此题是一道求逆序对数量的题目，我们利用归并排序

Code

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>#include<vector>typedef long long ll;
const int N = 1e5+5;
using namespace std;
ll q[N], tmp[N],ans;
void count_invertion(ll l,ll r) {//求逆序对数量//归并排序模版if (l >= r) return;
    ll t=0;
    ll mid = l + (r - l) / 2;
    count_invertion(l, mid);
    count_invertion(mid + 1, r);
    ll i = l, j = mid + 1;
    while (i <=mid && j <= r) {
        if (q[i] > q[j]) {//存在逆序
            ans += mid - i + 1;
            tmp[t++] = q[j++];
        }
        else tmp[t++] = q[i++];
    }

    while (i <= mid) tmp[t++] = q[i++];
    while (j <= r) tmp[t++] = q[j++];
    for (int i = l, j = 0; i <= r; i++,j++) q[i] = tmp[j];
}
int main(){
    ll n, k;
    while (cin >> n >> k)
    {
        for (int i = 0; i < n; i++) scanf("%d", &q[i]);
        ans=0;
        count_invertion(0,n-1);
        if (ans <= k) cout << 0 << endl;
     // 当ans小于等于k，在k次变换内数组q就会变得有序else cout << ans - k << endl;
    }
}

​