CF1183F Topforces Strikes Back(贪心)

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

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

Ⅱ

如果选两个数和,一定选掉最大的那个数

证明如下

①

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

②

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

③

若两个数都是的约数,那么最大就是

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

Ⅲ.

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

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

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

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

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

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

,确实此时需要特判一下

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

所以贪心策略就出来了

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

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

然后如果存在的情况,就取个即可

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

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

#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();
    }
}