CF 1183F [Topforces Strikes Back] 题解

前言

这道题目是一道非常巧妙的贪心。

难度：4星

简略题意：

给定一个长度为 $n$ 的序列,在序列中取至多三个数，使得这取的数互不为倍数关系。 $a[]$ ， $a_i <= 2 * 10 ^ 5 , n <= 2 * 10 ^ 5$

具体做法：

因为是最多取 3 个数，不妨按取的数的个数进行分类讨论。

$Case 1$ ：取一个数

这样的话当然是取最大的那个数最优，Pass。

$Case 2$ ：取两个数

通过手玩几组样例后，我们发现最大的那个数总是出现在取两个数得到的最大值中。于是大胆猜想，最后的答案一定会包含最大的数。

首先约定最大的数为 $Max$

接下来我们严谨证明这一点：

证明： $a + b <= c + Max$ （ $a , b$ 不能为最大值, $a != b,c$ 有可能取不到）

这时候，进行分类讨论：

倘若 $a,b$ 都是 $Max$ 的因子， $a,b$ 不同，所以 $max(a + b)$ = $\frac{Max}{2} + \frac{Max}{3}$ ，不等式成立。这时候显然应该取 $Max$ 能得到最优解，那么无法构造一个序列使得等式不成立。

倘若 $a,b$ 其中一个是 $Max$ 的因子，可以使得等式右边的那个 $c$ 等于 $a,b$ 中不是 $Max$ 的因子的数，不等式成立。这时候应该取 $Max + c$ 能得到最优解。

倘若 $a,b$ 都不是 $Max$ 的因子, 我们可以使得等式右边的那个 $c$ 等于 $a,b$ 中较大的不是 $Max$ 的因子的数，不等式成立。这时候显然应该取 $Max + c$ 能得到最优解。

所以两个数的情况的最大值无论如何都会包含 $Max$ 。

因此两个数的做法就是：取序列中的最大值，然后取不是 $Max$ 的因子的数中的最大值，两个数相加得到两个数的情况的最优解。

$Case 3$ ：取三个数。

这是一个重头戏。

根据我们在 $Case 2$ 中证明的结论来看，我们第三个情况也应该朝那个方向思考。

假设取三个数 :

$a + b + c <= d + e + Max$ ( $a,b,c$ 互不为倍数关系并且小于等于最大值 $Max$ , $d,e$ 有可能取不到)

倘若 $a,b,c$ 都是 $Max$ 的因子。那么 $max(a + b + c)$ = $\frac{Max}{2} + \frac{Max}{3} +\frac{Max}{5} = \frac{31Max}{30}$ ,不难发现这个情况下，构造一个序列，其中的所有数都是 $Max$ 的因子，取 $a + b + c$ 是优于取 $Max + d + e$ 的(d + e不存在)。因此在这种情况下不等式有可能不成立，于是我们特判一下是否同时存在 $\frac{Max}{2},\frac{Max}{3},\frac{Max}{5}$ 。
倘若 $a,b,c$ 其中一个不是 $Max$ 的因子，那么不妨令等式的右边的 $d,e$ 中任意一个等于这个非 $Max$ 的因子的数，那么就转化到了 $Case2$ 中两个数都是 $Max$ 的因子的情况，不再赘述。这时候取 $Max + d + e$ 取得最优解。
倘若 $a,b,c$ 其中两个不是 $Max$ 的因子，那么不妨令等式的右边的 $d,e$ 等于这两个非 $Max$ 的因子的数，剩下的一个数必然小于等于 $Max$
倘若 $a,b,c$ 三个都不是 $Max$ 的因子，同上面两个不是 $Max$ 的因子的情况，不再赘述。

所以说：取三个数的做法就是：首先特判一下是否存在 $\frac{Max}{2},\frac{Max}{3},\frac{Max}{5}$ 都为 $Max$ 的因子，这种情况下对于答案取一个 $max$ ，使得情况如果存在就被考虑。接下来取 $Max$ ，然后删去所有 $Max$ 的因子（要取 $Max$ 的话， $Max$ 的因子一定不出现在最后答案里面）

接下来就变成了取两个数的情况。

在剩下的数里面仍然取 $Max$ ，按照两个数的做法做即可。

Code

#include <bits/stdc++.h>
using namespace std; 
const int MAXN = 2e5 + 50;
int arr[MAXN],n;
int ST[MAXN],T[MAXN];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main()
{
    int Q;
    cin >> Q;
    for(int v = 1 ; v <= Q ; v ++)
    {
        n = read();
        for(int i = 1 ; i <= n ; i ++)
            arr[i] = read(),ST[arr[i]] = arr[i];
        sort(arr + 1 , arr + 1 + n);
        int Ans = arr[n],Max = arr[n];
        //上面是取两个数的最大情况。
        int f2 = 0,f3 = 0,f5 = 0;
        if(Max % 5 == 0 && ST[Max / 5] != 0) f5 = 1; //ST是一个桶
        if(Max % 3 == 0 && ST[Max / 3] != 0) f3 = 1; 
        if(Max % 2 == 0 && ST[Max / 2] != 0) f2 = 1;
        if(f2 && f3 && f5)
        Ans = max(Ans,Max / 5 + Max / 3 + Max / 2);//特判
        for(int i = 1 ; i <= n ; i ++)
        {
            T[i] = arr[i];
            if(arr[n] % T[i])
            Ans = max(Ans,arr[n] + T[i]);
        }//这里是取两个数的情况，答案取个max
        for(int i = 1 ; i <= n ; i ++)//首先取Max，删掉Max的因子
            if(Max % T[i] == 0) T[i] = 2e9;
        int M = 0;
        for(int i = 1 ; i <= n ; i ++)
            if(T[i] != 2e9)M = max(M,T[i]);//找出剩下的数的里面的最大值
        for(int i = 1 ; i <= n ; i ++)//按照两个数的做法做
            if(M % T[i] != 0 && T[i] != 2e9) Ans = max(Ans,Max + M + T[i]);
        cout << Ans << endl;
        for(int i = 1 ; i <= n ; i ++)
            ST[arr[i]] = 0;//多组数据，清空桶
    }
    return 0;
}

但是事实上，上面的做法浪费了时间在sort上，我们其实并不需要sort。时间复杂度是可以做到 O(n) 的

于是贴上 O(n) 的代码：

#include <bits/stdc++.h>
using namespace std; 
const int MAXN = 2e5 + 50;
int arr[MAXN],n;
int ST[MAXN],T[MAXN];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main()
{
    int Q;
    cin >> Q;
    for(int v = 1 ; v <= Q ; v ++)
    {
        n = read();
        for(int i = 1 ; i <= n ; i ++)
            arr[i] = read(),ST[arr[i]] = arr[i];
        int Ans = -1,Max = -1;
        for(int i = 1 ; i <= n ; i ++)
            Max = max(arr[i],Max);
        Ans = Max;
        //上面是取两个数的最大情况。
        int f2 = 0,f3 = 0,f5 = 0;
        if(Max % 5 == 0 && ST[Max / 5] != 0) f5 = 1; //ST是一个桶
        if(Max % 3 == 0 && ST[Max / 3] != 0) f3 = 1; 
        if(Max % 2 == 0 && ST[Max / 2] != 0) f2 = 1;
        if(f2 && f3 && f5)
        Ans = max(Ans,Max / 5 + Max / 3 + Max / 2);//特判
        for(int i = 1 ; i <= n ; i ++)
        {
            T[i] = arr[i];
            if(Max % T[i])
            Ans = max(Ans,Max + T[i]);
        }//这里是取两个数的情况，答案取个max
        for(int i = 1 ; i <= n ; i ++)//首先取Max，删掉Max的因子
            if(Max % T[i] == 0) T[i] = 2e9;
        int M = 0;
        for(int i = 1 ; i <= n ; i ++)
            if(T[i] != 2e9)M = max(M,T[i]);//找出剩下的数的里面的最大值
        for(int i = 1 ; i <= n ; i ++)//按照两个数的做法做
            if(M % T[i] != 0 && T[i] != 2e9) Ans = max(Ans,Max + M + T[i]);
        cout << Ans << endl;
        for(int i = 1 ; i <= n ; i ++)
            ST[arr[i]] = 0;//多组数据，清空桶
    }
    return 0;
}

两份代码貌似没有什么变化，主要就是一个用了sort，一个没有