CF1183 F.Topforces Strikes Back【数学】

题目链接：codeforces1183F Topforces Strikes Back

题解

分情况讨论，

  1. 选一个数，一定是选最大的那个数，假设是 。

  2. 选两个数，再选的这个数一定是最大的不是 的约数的数，假设是 。

    证明：

    假设当前两个数是 ，。

    1. 如果其中有一个是 的约数，则用 替换这个数。
    2. 如果两个都不是 的约数，则用 替换 。
    3. 如果两个都是 的约数，有 ，则只取 即可。

  3. 选三个数，第三个数一定是最大的不是 的约数的数，假设是 。但从上面的证明可以看出，有 ，这个时候我们只要判断是否存在这种情况，取最大值就好了。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], flag[3];
vector<int> v;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a+1, a+1+n);
        int ans = a[n];
        for (int i = 1; i <= n; i++) {
            if (a[n] % a[i] != 0) v.push_back(a[i]);
            if (a[i] == a[n]/2 && a[n] % a[i] == 0) flag[0] = 1;
            if (a[i] == a[n]/3 && a[n] % a[i] == 0) flag[1] = 1;
            if (a[i] == a[n]/5 && a[n] % a[i] == 0) flag[2] = 1;
        }
        int len = v.size();
        if (len) ans += v[len-1];
        for (int i = len-2; i >= 0; i--) {
            if (v[len-1] % v[i] != 0) {ans += v[i]; break;}
        }
        if (flag[0] && flag[1] && flag[2]) ans = max(ans, a[n]*31/30);
        cout << ans << endl;
        memset(flag, 0, sizeof(flag));
        v.clear();
    }
    return 0;
}