HDOJ 1394 Minimum Inversion Number：循環數組最小逆序數 (暴力 + 公式優化)

問題描述

給定 0~n-1 的一個排列，將其前 m 個元素移到末尾形成新排列 (m=0..n-1)，求所有循環移位中逆序數的最小值。n≤5000。

核心公式：循環移位逆序數變化規律

設原排列逆序數為 inv0。將第一個元素 x = a[0] 移到末尾：

• 原本 x 前面有 x 個比它小的數 (0~x-1)，後面有 n-1-x 個比它大的數 (x+1~n-1)。
• 移至末尾後，x 不再與前面的數構成逆序對，減少 x 個逆序；與後面的數構成逆序對，增加 n-1-x 個逆序。
• 新逆序數 inv1 = inv0 - x + (n-1-x) = inv0 + n - 1 - 2*x。

遞推：inv_{k+1} = inv_k + n - 1 - 2*a[k]。

算法流程

1. 計算初始逆序數 inv0 (O(n²) 暴力或 O(n log n) BIT，n=5000 暴力 12.5e6 可過)。
2. 利用公式 O(n) 遞推計算所有循環移位的逆序數，取最小值。

關鍵代碼 (C++ 暴力初始 + 公式遞推)

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector a(n);
        for (int i=0; i a[j]) inv++;

        int minInv = inv;
        for (int i=0; i

複雜度分析

初始逆序數：O(n²) = 25e6 操作 (n=5000)，C++ 約 0.2s 可過。
遞推：O(n)。
總體：O(n²)，無需線段樹/BIT，代碼極短。


線段樹優化（補充）
若 n 更大 (如 1e5)，初始逆序數需用 BIT/線段樹 O(n log n) 計算。遞推公式不變。

總結
HDOJ 1394 展示了循環移位逆序數的精妙數學規律：Δ = n - 1 - 2*x。將 O(n²) 遞推降為 O(n)，配合暴力初始計算，是 n=5000 時最簡潔有效的解法。理解逆序對變化的組合本質，是解決此類排列統計問題的關鍵。