HDU 4911 Inversion(歸並求逆序對)

HDU 4911 Inversion

題目鏈接

題意：給定一個數組，可以相鄰交換最多k次，問交換後，逆序對為多少

思路：先利用歸並排序求出逆序對，然後再減去k就是答案

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 100005;
int n, num[N], save[N], sn;

void init() {
    for (int i = 0; i < n; i++)
	scanf("%d", &num[i]);
}

long long solve(int l, int r, int *num) {
    if (r - l < 1) return 0;
    int mid = (l + r) / 2;
    long long ans = solve(l, mid, num) + solve(mid + 1, r, num);
    sn = l;
    int ll = l, rr = mid + 1;
    while (ll <= mid && rr <= r) {
	if (num[ll] <= num[rr])
	    save[sn++] = num[ll++];
	else {
	    ans += (mid + 1 - ll);
	    save[sn++] = num[rr++];
	}
    }
    while (ll <= mid) save[sn++] = num[ll++];
    while (rr <= r) save[sn++] = num[rr++];
    for (int i = l; i <= r; i++)
	num[i] = save[i];
    return ans;
}

long long k;

int main() {
    while (~scanf("%d%I64d", &n, &k)) {
	init();
	long long ans = solve(0, n - 1, num);
	ans = max(ans - k, 0LL);
	printf("%I64d\n", ans);
    }
    return 0;
}