CF1183F Topforces Strikes Back(贪心)

非常巧妙的题(~~然而有什么用嘛!!!!我又不会~~)

$Ⅰ$

如果只选一个数,一定选最大的数

Ⅱ

如果选两个数 $a$ 和 $b$ ,一定选掉最大的那个数 $x$

证明如下

①

若只有一个数是 $x$ 的约数,那么拿 $x$ 去替换他

②

若两个数都不是 $x$ 的约数,替换任何一个数都会时答案更优

③

若两个数都是 $x$ 的约数,那么最大就是 $\frac{x}{2}+\frac{x}{3}<x$

综上所诉,选择最大的 $x$ 才是最优的.

Ⅲ.

选择三个数最大,有了上面的铺垫就不难推了.此时要不要选最大的数呢??

若三个数都不是 $x$ 的约数,替换任何一个都会更优

若三个数只有一个是 $x$ 的约数,替换掉会更优

若三个数有两个是 $x$ 的约数,那么最大可以是

$\frac{x}{2}+\frac{x}{3}+c$

而我只要选 $x$ 和 $c$ 就可以否定掉这个答案。

若三个数都是 $x$ 的约数,最大的情况

$\frac{x}{2}+\frac{x}{3}+\frac{x}{5}=\frac{31}{30}x$ ,确实此时需要特判一下

但是稍微次一点,又回到了必须选 $x$ 的情况

$\frac{x}{2}+\frac{x}{3}+\frac{x}{7}=\frac{41}{42}x<x$

所以贪心策略就出来了

先选择最大的 $x$ ,然后把所有 $x$ 的约数筛掉

再选择最大的数,再次筛掉约数...再选最大的数

然后如果存在 $\frac{x}{2}+\frac{x}{3}+\frac{x}{5}$ 的情况,就取个 $max$ 即可

总之,能想到Ⅱ,问题就迎刃而解了

主要还是这种贪心的思维和替换法....

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int q,n,a[maxn],ok[4];
vector<int>v;
map<int,int>mp;
int main()
{
    cin >> q;
    while( q-- )
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)    scanf("%d",&a[i] );
        sort( a+1,a+1+n );
        int ans = a[n],temp = 0;
        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]%2==0 )    ok[1] = 1;
            if( a[i]==a[n]/3&&a[n]%3==0 )    ok[2] = 1;
            if( a[i]==a[n]/5&&a[n]%5==0 )    ok[3] = 1;
        }
        int siz1 = v.size();
        if( siz1 )    ans += v[siz1-1];
        for(int i=siz1-2;i>=0;i--)
            if( v[siz1-1]%v[i]!=0 )    { ans+=v[i]; break; }
        if( ok[1]&&ok[2]&&ok[3] )    ans = max( ans,a[n]/30*31 );
        printf("%d\n",ans);
        ok[1] = ok[2] = ok[3] = 0;  v.clear();
    }
}