HDU 5493：Queue（隊列重構，二分 + 樹狀數組）

一、題目大意

n 人排隊，身高互不相同。已知每人身高及他前面/後面比他高的人數（不知是前是後）。要求還原隊列且字典序最小。

二、解題思路

按身高從小到大排序處理。對於第 i 高的人（已處理 i-1 個更矮的人），他前面/後面有 k 個更高的人。剩餘 n-i 個更高的人中，若他在第 p+1 個空位，則 p = min(k, n-i-k) 以保證字典序最小。若 n-i-k < 0 無解。
用 BIT 維護空位：bit[x]=1 表示位置 x 已佔。二分查找第 p+1 個空位：mid - sum(mid) >= p+1。

三、代碼實現（C++）

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int T, n;
int bit[MAXN], ans[MAXN];
struct Node { int h, k; bool operator<(Node o) const { return h < o.h; } } a[MAXN];

int sum(int x) { int s=0; while(x){ s+=bit[x]; x-=x&-x; } return s; }
void add(int x, int v) { while(x<=n){ bit[x]+=v; x+=x&-x; } }

int main() {
    scanf("%d", &T);
    for (int cs=1; cs<=T; ++cs) {
        scanf("%d", &n);
        for (int i=1; i<=n; ++i) scanf("%d%d", &a[i].h, &a[i].k);
        sort(a+1, a+n+1);
        memset(bit, 0, sizeof(int)*(n+2));
        bool ok = true;
        for (int i=1; i<=n; ++i) {
            int k = a[i].k;
            if (n - i - k < 0) { ok = false; break; }
            int p = min(k, n - i - k) + 1; // 第 p 個空位
            int l=1, r=n, mid;
            while (l < r) {
                mid = (l+r)/2;
                if (mid - sum(mid) >= p) r = mid;
                else l = mid+1;
            }
            add(l, 1);
            ans[l] = a[i].h;
        }
        printf("Case #%d:", cs);
        if (ok) { for (int i=1; i<=n; ++i) printf(" %d", ans[i]); puts(""); }
        else puts(" impossible");
    }
    return 0;
}

四、複雜度分析

• 時間：O(n log² n) (排序 + n 次二分 × BIT 查詢)
• 空間：O(n)

核心技巧：排序+貪心選最小位置+BIT 加速空位查找。