HDU 5443 The Water Problem：區間最大值查詢——暴力解法通過

HDU 5443 The Water Problem：區間最大值查詢——暴力解法通過

題目描述

在缺水之地，水源極其珍貴。給定 n 個水源，大小為 a₁..a_n。q 個查詢，每個查詢給出 l, r，求區間 [l, r] 內最大水源大小。
限制：T≤10, n≤1000, q≤1000, a_i∈[1, 10⁶]。

輸入輸出範例

輸入：
3
1
100
1
1 1
1
5
1 2 3 4 5
5
1 2
1 3
2 4
3 4
3 5
3
1 999999
1
4
1 1
1 2
2 3
3 3

輸出：
100
2
3
4
4
5
1
999999
999999
1

解題思路

標準解法為線段樹或稀疏表（RMQ），單次查詢 O(log n) 或 O(1)。但本題 n, q 均 ≤ 1000，暴力掃描區間最大值僅需 O(n×q) = 10⁶ 量級，完全在時限內，代碼極簡，無需複雜數據結構。

暴力算法

1. 讀入陣列 a[1..n]。
2. 對每個查詢 [l, r]，初始化 max = 0，循環 i=l..r 更新 max = max(max, a[i])。
3. 輸出 max。

參考代碼 (C++)

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int a[1010];
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int q;
        scanf("%d", &q);
        while (q--) {
            int l, r;
            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);
        }
    }
    return 0;
}

複雜度分析

• 時間：O(T × (n + q × n)) ≤ 10 × (1000 + 1000×1000) ≈ 10⁷ 操作，極快。
• 空間：O(n)。

若 n, q 擴大到 10⁵，則需線段樹/稀疏表。本題數據範圍小，暴力最優（開發效率最高）。