题解 CF1183F 【Topforces Strikes Back】

## 题意 从$n$个数中选出来最多$3$个数，使得这三个数中不存在任意一个数是另一个数的倍数，同时使得这三个数的和最大。 ## 题解 这是一道十分巧妙的贪心题。 首先我们将答案按照选出来的数字个数分情况。 ### 一 如果选出来的数字个数为$1$，显然答案就是最大的数字。 ### 二 如果选出来的数字个数为$2$，我们考虑最大的数$a$是否在最优答案里。 答案是肯定的，因为如果选出来的两个数$x,y$都不是$a$，那么这样的答案一定不会更大。证明如下： 1、如果有一个数不是$a$的因数，那么直接用$a$替换这个数。 2、如果两个数都是$a$的因数，那么这两个数的和最大是$\dfrac a2+\dfrac a3<a$，也就是说我们在步骤一中就已经得到最优解了。 所以对于这一种情况，我们只需要选出来最大的数，然后从剩下的数中找到一个不是它的因数的最大的数即可。 ### 三 如果选出来的数字个数为$3$，我们还是考虑最大的数$a$是否在最优答案里。 可以发现，如果选出来的三个数中有一个或两个数不是$a$的因数，那么就可以由情况二进行证明，一定要选出来$a$。 而如果三个数都是$a$的因数，我们发现有唯一的一种特殊情况：$\dfrac a2+\dfrac a3+\dfrac a5>a$，其余的都小于$a$。 所以我们需要特判一下$\dfrac a2+\dfrac a3+\dfrac a5$这种情况，特判完后就选出来最大的$a$并把它所有的因数删掉，然后用情况二中的方法来做。 时间复杂度$O(n)$。 ```cpp #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int t,n,a[200005]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); int ans=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); ans=max(ans,a[i]); } sort(a+1,a+n+1); int an=a[n]; bool flag1=0,flag2=0,flag3=0; for(int i=1;i<=n;i++) { if(a[i]*2==an)flag1=1; if(a[i]*3==an)flag2=1; if(a[i]*5==an)flag3=1; } if(flag1&&flag2&&flag3)ans=max(ans,an/2+an/3+an/5); for(int i=1;i<=n;i++) if(a[n]%a[i]==0)a[i]=2000000000; sort(a+1,a+n+1); while(a[n]==2000000000)n--; ans=max(ans,an+a[n]); for(int i=1;i<=n;i++) if(a[n]%a[i]!=0)ans=max(ans,an+a[n]+a[i]); printf("%d\n",ans); } return 0; } ```