ZOJ 1484 Minimum Inversion Number——歸並排序求逆序數 + 循環移動公式 O(n log n)

問題描述

給定 0~n-1 的一個排列（n ≤ 5000）。定義逆序對數為 `ia[j]` 的對數。考慮將前 m 個元素移到末尾（m=0..n-1）得到 n 個循環序列。求這 n 個序列中的最小逆序對數。

核心公式

設原序列逆序對數為 `inv0`。將首元素 `x = a[0]` 移到末尾：

• 失去的逆序對：`x` 與後面比它小的元素 → 數量 = `x`（因為排列是 0~n-1，比 x 小的恰有 x 個）。
• 新增的逆序對：`x` 與後面比它大的元素 → 數量 = `n-1-x`。
• 遞推：`inv_{k+1} = inv_k - x + (n-1-x) = inv_k + n - 1 - 2*x`，其中 `x = a[k]`（原序列第 k 個元素）。

算法流程

1. 歸並排序求初始逆序對 `inv0`（O(n log n)）。
2. 遍歷 k=0..n-2，按公式遞推計算 `inv_{k+1}`，維護最小值。
3. 輸出最小值。

代碼實現

#include 
using namespace std;
const int MAXN = 5005;
int a[MAXN], tmp[MAXN];
long long inv;

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 = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            inv += mid - i + 1; // a[i..mid] 都 > a[j]
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    copy(tmp+l, tmp+r+1, a+l);
}

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

關鍵點

• 排列性質：元素恰為 0~n-1，比 `x` 小的數量恆為 `x`，大的為 `n-1-x`，無需 BIT/線段樹維護。
• 長長整型：逆序對數最大 ~12.5×10⁶，需 `long long`。
• 歸並排序求逆序對：經典模板，合併時 `a[i] > a[j]` 產生 `mid-i+1` 個逆序對。
• 遞推公式推導：移動首元素 `x`，失去 `x` 個逆序對（`x` 與比它小的），獲得 `n-1-x` 個（`x` 與比它大的）。

複雜度

• 時間：O(n log n) 求初始逆序對 + O(n) 遞推 = O(n log n)。
• 空間：O(n)。

總結

循環移動逆序對最小值。利用排列 0~n-1 的特殊性質，首元素移動的逆序對變化量有閉式公式，避免了重複計算。歸並排序求初始逆序對 + O(n) 遞推，完美應對 n=5000。