CodeForces 1183F Topforces Strikes Back

题意

从$n$个数中选出来最多$3$个数，使得这三个数中不存在任意一个数是另一个数的倍数，同时使得这三个数的和最大。

分析

设最大数为$maxx$

取一个数，取$maxx$
取两个数，假设不取$maxx$，则两个数皆为$maxx$的因数，否则可用$maxx$替换某个因数，而最大为$\frac{maxx}{2}+\frac{maxx}{3}<maxx$，因此必须选$maxx$，另一个挑最大即可
取三个数，如果三个数皆为$maxx$的因数，则只有$\frac{maxx}{2}+\frac{maxx}{3}+\frac{maxx}{5}>maxx$满足，特判后取到$maxx$，并将$maxx$的所有因数标为不可取，然后就是取两个数的情况了

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;

int a[maxn];

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    rep(i, 1, n)cin >> a[i], ans = max(a[i], ans);
    sort(a + 1, a + n + 1);
    int maxx = a[n];
    bool flag1 = false, flag2 = false, flag3 = false;
    rep(i, 1, n) {
        if (a[i] * 2 == maxx)
            flag1 = true;
        if (a[i] * 3 == maxx)
            flag2 = true;
        if (a[i] * 5 == maxx)
            flag3 = true;
    }
    if (flag1 && flag2 && flag3)
        ans = max(ans, maxx / 2 + maxx / 3 + maxx / 5);
    rep(i, 1, n)if (a[n] % a[i] == 0)a[i] = -1;
    sort(a + 1, a + n + 1);
    ans = max(ans, maxx + a[n]);
    rep(i, 1, n)
        if (a[i] != -1 && a[n] % a[i] != 0)
            ans = max(ans, maxx + a[n] + a[i]);
    cout << ans << '\n';
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}