Codeforces 474B Worms 蠕蟲堆查詢問題解法

Codeforces Round #271 Div.2 B - Worms 題目解析

有 n 堆蠕蟲，第 i 堆有 aᵢ 條，所有蠕蟲按順序編號 1 到 Σaᵢ。給出 m 個查詢，每個查詢一個蠕蟲標號 qⱼ，求該蠕蟲所在的堆編號。n, m ≤ 10⁵，總蠕蟲數 ≤ 10⁶。

前綴和 + 直接映射法

由於總蠕蟲數 ≤ 10⁶，可開陣列 num[10⁶]，預處理每個標號對應的堆編號。遍歷各堆，將對應範圍填入堆號。查詢時 O(1) 直接訪問。

C++ 代碼實現

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e6;
int num[maxn];

int main() {
    int n;
    scanf("%d", &n);
    int cnt = 0, m;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &m);
        for (int j = 0; j < m; j++)
            num[++cnt] = i;
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &m);
        printf("%d\n", num[m]);
    }
    return 0;
}

替代方案：前綴和 + 二分查找

若總數較大，可構建前綴和數組 sum[i] 表示前 i 堆蠕蟲總數，查詢時二分查找第一個 sum[pos] ≥ q 的位置，時間複雜度 O(m log n)。

複雜度對比