10125 Sumsets

題目連結

題目翻譯

給定一個整數集合 S，請找出最大的 d，使得存在集合中四個相異的元素 a、b、c、d，滿足 a + b + c = d。

輸入

有多組測資，每組第一行是整數 n（1 ≤ n ≤ 1000），代表集合大小，接下來 n 行是集合中的元素，每個元素互不相同，範圍在 -536870912 到 536870911 之間。輸入以 n = 0 結束。

輸出

每組測資輸出一行最大的 d；若不存在這樣的組合，輸出 no solution。

解題思路

先用雜湊表 (unordered_map) 把所有「兩數之和」v[i] + v[j]（i ≠ j）記下來，對應儲存下標組合 (i, j)。接著再次枚舉 i、j（i ≠ j），計算差值 v[i] - v[j]：如果這個差值曾經是某兩個元素 v[k1] + v[k2] 的和，且 i、j、k1、k2 四個下標兩兩不同，就代表 v[k1] + v[k2] + v[j] = v[i]，也就是找到了一組 a + b + c = d（其中 d = v[i]）。用 mx 持續記錄所有合法解中最大的 v[i]，最後若找不到任何合法組合則輸出 no solution。

程式碼

//author: Piau
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define int long long
#define PII pair<int, int>

signed main() { WA();
    for (int n; cin >> n, n;) {
        vector<int> v(n);
        for (auto &i : v) cin >> i;
        unordered_map<int, vector<PII>> mp;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                mp[v[i]+v[j]].pb({i, j});
            }
        }
        int mx = -INF;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (mp.count(v[i]-v[j])) for (auto &k : mp[v[i]-v[j]]) {
                    if (i != k.fi && i != k.se && j != k.fi && j != k.se) mx = max(mx, v[i]);
                }
            }
        }
        if (mx == -INF) cout << "no solution\n";
        else cout << mx << '\n';
    }
}