HDU 2141「Can you find it?」：三數組求和優化解法（排序+二分查找）

HDU 2141「Can you find it?」：三數組求和優化解法

問題描述：給定三個數組 A、B、C（長度 ≤ 500）及 S 個查詢值 X（S ≤ 1000），判斷是否存在 Ai + Bj + Ck = X。若存在輸出 YES，否則 NO。

算法分析

暴力三重循環 O(L·N·M) 達 1.25 億次，極易超時。優化策略：

1. 將數組 C 排序（O(M log M)）。
2. 雙重循環枚舉 A、B 所有組合和 k = Ai + Bj（O(L·N)）。
3. 對每個查詢 X，在 C 中二分查找 X - k（O(log M)）。
4. 總複雜度：O(L·N·log M + S·L·N·log M) ≈ 225 萬次操作，輕鬆通過。

完整代碼實現

#include <stdio.h>
#include <stdlib.h>

int a[501], b[501], c[501], ab[250001];

int cmp(const void *p1, const void *p2) { return *(int*)p1 - *(int*)p2; }

int binary_search(int arr[], int len, int target) {
    int l = 0, r = len - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (arr[mid] == target) return 1;
        arr[mid] < target ? (l = mid + 1) : (r = mid - 1);
    }
    return 0;
}

int main() {
    int L, N, M, S, caseNo = 1;
    while (scanf("%d %d %d", &L, &N, &M) != EOF) {
        for (int i = 0; i < L; ++i) scanf("%d", &a[i]);
        for (int i = 0; i < N; ++i) scanf("%d", &b[i]);
        for (int i = 0; i < M; ++i) scanf("%d", &c[i]);
        qsort(c, M, sizeof(int), cmp);

        int abSize = 0;
        for (int i = 0; i < L; ++i)
            for (int j = 0; j < N; ++j)
                ab[abSize++] = a[i] + b[j];
        qsort(ab, abSize, sizeof(int), cmp);

        scanf("%d", &S);
        printf("Case %d:\n", caseNo++);
        while (S--) {
            int X; scanf("%d", &X);
            int found = 0;
            for (int i = 0; i < M && !found; ++i) {
                if (binary_search(ab, abSize, X - c[i])) found = 1;
            }
            puts(found ? "YES" : "NO");
        }
    }
    return 0;
}

關鍵優化點

• 預計算 A+B 所有和並排序，將三數求和轉化為兩數求和問題。
• 對每個查詢遍歷 C 數組，在 AB 中二分查找，利用有序性提前剪枝。
• 使用 qsort 和手寫二分查找，無額外庫依賴，適配 OJ 環境。

此解法在時空效率與代碼複雜度之間取得良好平衡，是 ACM 類問題中「排序+二分」經典模式的典型應用。