HDU 4911 Inversion：最多 K 次相鄰交換後的最小逆序數

HDU 4911 Inversion：最多 K 次相鄰交換後的最小逆序數

給定長度 n ≤ 1e5 的序列，允許最多 k ≤ 1e9 次相鄰元素交換，求可能得到的最小逆序數。

核心觀察

• 一次相鄰交換最多減少 1 個逆序對（將較大元素向右移動）。
• 因此最小逆序數 = max(0, 初始逆序數 - k)。
• 問題轉化為：高效計算初始逆序數。

歸並排序求逆序數

在歸並過程中，當左半部分元素 a[i] > a[j]（右半部分元素）時，說明 a[i] 及其右側所有左半部分元素都與 a[j] 構成逆序對，數量為 mid - i + 1。

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid+1, r);
    int i = l, j = mid+1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            ans += mid - i + 1; // 關鍵：累加逆序對
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (i = l, k = 0; i <= r; i++, k++) a[i] = tmp[k];
}

完整解法

int main() {
    while (scanf("%d%d", &n, &k) != EOF) {
        ans = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        merge_sort(1, n);
        printf("%lld\n", max(0LL, ans - k));
    }
    return 0;
}

複雜度與注意點

• 時間 O(n log n)，空間 O(n)，滿足 n=1e5。
• ans 需用 long long，最大逆序數 ~ 5e9。
• 歸並排序比樹狀數組/線段樹代碼更短、常數更小，適合此類純逆序數統計。

此題展示了「逆序數性質 + 歸並排序」的經典組合：先算初始值，再用交換上界直接得答案，無需模擬交換過程。