POJ 2182 Lost Cows 詳解

題目：N (≤8000) 頭牛，品牌 1..N。輸入 N-1 個數 a[i]（i=2..N），表示第 i 位牛前面比它小的牛的數量。第 1 位牛無此數據（隱含 0）。求原始排列。

核心洞察：逆向構造 + BIT 查找第 k 小可用數

從後向前確定每位牛的品牌：
- 第 N 位：前面有 a[N] 個更小的數，說明它是剩餘數中 第 a[N]+1 小 的數。
- 確定後移除該數，處理 N-1 位，以此類推。
- 第 1 位：剩餘唯一數。

樹狀數組實現「查找第 k 小」

BIT 維護可用數的標記（1=可用，0=已用）。初始全部 1。
find_kth(k)：二分/下標查找最小 x 使 sum(x) ≥ k。
標準 BIT 二分：

int find_kth(int k) {
    int idx = 0;
    for (int d = 1<<13; d; d >>= 1) { // 2^13=8192 > 8000
        int next = idx + d;
        if (next <= N && bit[next] < k) {
            idx = next;
            k -= bit[next];
        }
    }
    return idx + 1;
}

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 8005;
int bit[MAXN], ans[MAXN], a[MAXN];
int N;

void add(int x, int v) { for(; x<=N; x+=x&-x) bit[x]+=v; }
int sum(int x) { int r=0; for(; x>0; x-=x&-x) r+=bit[x]; return r; }
int find_kth(int k) {
    int idx = 0;
    for (int d = 1<<13; d; d >>= 1) {
        int next = idx + d;
        if (next <= N && bit[next] < k) {
            idx = next;
            k -= bit[next];
        }
    }
    return idx + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> N) {
        a[1] = 0;
        for (int i = 2; i <= N; ++i) cin >> a[i];
        fill(bit, bit+N+1, 0);
        for (int i = 1; i <= N; ++i) add(i, 1);
        for (int i = N; i >= 1; --i) {
            ans[i] = find_kth(a[i] + 1);
            add(ans[i], -1);
        }
        for (int i = 1; i <= N; ++i) cout << ans[i] << '\n';
    }
    return 0;
}

關鍵測試

複雜度分析

總結

POJ 2182 是「逆向構造排列 + BIT 查找第 k 小」的經典應用。它展示了如何將「前面有多少個更小」的信息，轉化為「在剩餘數中選第 k 小」的操作。BIT 的 find_kth 是核心技能，亦可用線段樹、平衡樹實現。此模式適用於「逆序對還原、排名查詢、動態順序統計」等問題。