HDU 5443 The Water Problem：區間最大值暴力解法

題目大意

給定 n 個水源大小，q 次查詢，每次詢問區間 [l, r] 內的最大值。數據範圍：n, q ≤ 1000，T ≤ 10。

解法選擇：暴力枚舉

雖然區間最值通常用線段樹或 ST 表，但本題 n, q 均 ≤ 1000，單次查詢 O(n) 總複雜度 O(T·q·n) ≈ 10⁷，完全在時限內，無需複雜數據結構。

算法流程

1. 讀入 T。
2. 對每組案例：讀 n，讀入陣列 a[1..n]。
3. 讀 q，對每個查詢讀 l, r，循環 i=l..r 找最大值並輸出。

代碼骨架

int a[1010];
while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d", &l, &r);
        int mx = 0;
        for (int i = l; i <= r; ++i)
            if (a[i] > mx) mx = a[i];
        printf("%d\n", mx);
    }
}

複雜度與適用場景

• 時間：O(T·(n + q·n))，空間：O(n)。
• 當 n, q ≤ 10⁵ 時需改用線段樹（O(log n) 查詢）或 ST 表（O(1) 查詢，O(n log n) 預處理）。