HDU 1394 環狀序列最小逆序數 BIT解法

問題描述

給定長度為 n 的排列（元素為 0 到 n-1），視為環狀序列。共有 n 個長度為 n 的線性序列（每個元素作為起點一次）。求這 n 個序列中的最小逆序數。

核心洞察

設原序列逆序數為 inv。將首元素 a 移至序列末尾，逆序數變化為：

Δ = (比 a 大的元素個數) - (比 a 小的元素個數) = (n - 1 - a) - a = n - 1 - 2a

因此可 O(n) 依次計算所有輪轉序列的逆序數並取最小值。

算法流程

1. 用 BIT（樹狀數組）計算初始序列逆序數 inv
2. 令 ans = inv
3. 對於 i = 1 到 n-1：
   　　inv += n - 1 - 2·a[i]
   　　ans = min(ans, inv)
4. 輸出 ans

BIT 實現關鍵代碼

const int MAXN = 5005;
int C[MAXN], a[MAXN];

int lowbit(int x) { return x & -x; }

int query(int x) {
    int res = 0;
    while (x > 0) { res += C[x]; x -= lowbit(x); }
    return res;
}

void update(int x, int d) {
    while (x <= n) { C[x] += d; x += lowbit(x); }
}

// 計算初始逆序數
int inv = 0;
for (int i = 1; i <= n; ++i) {
    update(a[i] + 1, 1); // 值域 0..n-1，映射到 1..n
    inv += i - query(a[i] + 1);
}

複雜度分析

• 初始逆序數計算：O(n log n)
• 輪轉枚舉：O(n)
• 總時間：O(n log n)，空間：O(n)

注意事項

• 元素值域 0 到 n-1，BIT 下標需 +1 偏移
• 逆序數可能較大，建議用 long long 存儲
• 多組測試數據，直到 EOF