UVa 10125 Sumsets 解題詳解：排序+雙指針+枚舉優化求最大 d

問題描述

給定一個整數集合 S（|S| ≤ 1000），找出最大的元素 d ∈ S，使得存在 a, b, c ∈ S（可重複）滿足 d = a + b + c。若無解輸出 "no solution"。多測試用例，n = 0 結束。

核心算法：排序 + 逆向枚舉 + 雙指針

關鍵洞察

• 將等式變形：b + c = d - a
• 對集合升序排序後，d 從大到小枚舉（優先嘗試大值，找到即為答案）
• 對每個 d，a 也從大到小枚舉（使 d - a 盡可能小，提前剪枝）
• 固定 d, a 後，b, c 在剩餘元素中雙指針查找：b 從最小，c 從最大向中間收斂

去重與邊界處理

• 索引 l（d）、i（a）、j（b）、k（c）必須兩兩不同
• 負數存在時最小的元素也可能是 d，不可提前終止
• j < k 保證不重複使用同一元素兩次（除非集合本身有重複值）

完整 C++ 代碼

#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 1005;
int s[N], n, ans;

int find() {
    for (int l = n - 1; l >= 0; l--) {           // d 從大到小
        for (int i = n - 1; i > 0; i--) {        // a 從大到小
            if (l == i) continue;
            int sum = s[l] - s[i];               // 目標 b + c
            for (int j = 0, k = i - 1; j < k; ) { // 雙指針
                int temp = s[j] + s[k];
                if (temp > sum) k--;             // 和太大，c 左移
                else if (temp < sum) j++;        // 和太小，b 右移
                else { ans = s[l]; return 1; }   // 找到解
            }
        }
    }
    return 0;
}

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i++) scanf("%d", &s[i]);
        sort(s, s + n);
        if (find()) printf("%d\n", ans);
        else printf("no solution\n");
    }
    return 0;
}

複雜度分析

• 時間：O(n³) 最壞情況，但逆向枚舉 + 雙指針剪枝極其有效，實際運行極快（n=1000 通常 < 0.1s）
• 空間：O(n)

優化技巧總結

1. 排序先行：為雙指針與剪枝奠基
2. 逆向枚舉 d：找到即最優，無需遍歷所有
3. a 同向逆序：使 d - a 減小，雙指針更易命中
4. 雙指針 O(n) 替代三層循環 O(n²)
5. 索引去重：l != i、j < k 保證元素不同

本題是「排序+雙指針+枚舉順序優化」的教科書級範例，展示了如何將 O(n⁴) 暴力降維到實際可接受的 O(n³) 甚至更好。