HDU 3486 Interviewe - RMQ 區間最值優化分組策略

HDU 3486 Interviewe：RMQ 支援的貪心分組算法

題目要求：將面試者按順序分組，每組錄取一人，找到最小分組數使得錄取能力總和超過 K。N ≤ 200,000。

核心觀察

• 分組必須連續且保持原序
• 每組貢獻為組內最大值（錄取最強者）
• 目標：最小化分組數，使各組最大值之和 ≥ K

算法策略：二分答案 + RMQ 驗證

1. 對答案（分組數）進行二分搜尋
2. 固定分組數 g，判斷能否達成目標：

貪心驗證邏輯：

bool check(int groups) {
    int len = n / groups;        // 基礎組長
    int rem = n % groups;        // 前 rem 組多 1 人
    long long sum = 0;
    int pos = 0;
    for (int i = 0; i < groups; ++i) {
        int curLen = len + (i < rem ? 1 : 0);
        int maxVal = rmq_query(pos, pos + curLen - 1); // 區間最大值
        sum += maxVal;
        if (sum >= K) return true;
        pos += curLen;
    }
    return false;
}

RMQ (稀疏表) 實現

int dp[MAXN][LOGN]; // dp[i][j] 表示從 i 開始長度 2^j 的區間最大值

void RMQ_init() {
    for (int i = 1; i <= n; ++i) dp[i][0] = a[i];
    for (int j = 1; (1<