思路
归并排序(merge sort) or 树状数组(???)
划分区域l, mid, r
在mer_sort(l, r)中 如果出现前面元素大于后面 则 cnt += mid - i + 1(cnt 为逆序对数)
题目求min逆序对数, 即每一步都要减少一对逆序对, 输出max(cnt - k, 0)(可能步数很大最后0个逆序对数)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, k, cnt, a[N], b[N];
void mer_sort(ll l, ll r)
{
if(l >= r) return ;
ll mid = l + r >> 1;
mer_sort(l, mid);
mer_sort(mid + 1, r);
ll i = l, j = mid + 1, ii = 0;
while(i <= mid && j <= r)
{
if(a[i] > a[j])
{
b[ii ++ ] = a[j ++ ];
cnt += mid - i + 1;
}
else
b[ii ++ ] = a[i ++ ];
}
while(i <= mid) b[ii ++ ] = a[i ++ ];
while(j <= r) b[ii ++ ] = a[j ++ ];
for(i = 0; i < ii; i ++ )
a[i + l] = b[i];
}
int main()
{
while(cin >> n >> k)
{
cnt = 0;
for(int i = 0; i < n; i ++ ) cin >> a[i];
mer_sort(0, n - 1);
cout << (cnt > k ? cnt - k : 0) << endl;
}
return 0;
}