【每日一题】12月28日题目精讲
题号 NC113786
名称 Topforces Strikes Back
来源 CF1183F
戳我进入往期每日一题汇总贴~
往期每日一题二期题单
如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468
题解
作者：YangYL°
前言
这道题目是一道非常巧妙的贪心。
难度：4星
简略题意：
给定一个长度为 的序列,在序列中取至多三个数，使得这取的数互不为倍数关系。
，
具体做法：
因为是最多取 3 个数，不妨按取的数的个数进行分类讨论。
： 取一个数
这样的话当然是取最大的那个数最优，Pass。
：取两个数
通过手玩几组样例后，我们发现最大的那个数总是出现在 取两个数得到的最大值中。于是大胆猜想，最后的答案一定会包含最大的数。
首先约定最大的数为
接下来我们严谨证明这一点：
证明： （
不能为最大值,
有可能取不到）
这时候，进行分类讨论：
倘若 都是
的因子，
不同，所以
=
，不等式成立。这时候显然应该取
能得到最优解，那么无法构造一个序列使得等式不成立。
倘若 其中一个是
的因子，可以使得等式右边的那个
等于
中 不是
的因子的数，不等式成立。这时候应该取
能得到最优解。
倘若 都不是
的因子, 我们可以使得等式右边的那个
等于
中 较大的不是
的因子的数，不等式成立。这时候显然应该取
能得到最优解。
所以两个数的情况的最大值无论如何都会包含 。
因此两个数的做法就是：取序列中的最大值，然后取不是 的因子的数中的最大值，两个数相加得到两个数的情况的最优解。
： 取三个数。
这是一个重头戏。
根据我们在 中证明的结论来看，我们第三个情况也应该朝那个方向思考。
假设取三个数 :
(
互不为倍数关系并且小于等于最大值
,
有可能取不到)
倘若
都是
的因子。 那么
=
,不难发现这个情况下，构造一个序列，其中的所有数都是
是优于取
的(d + e不存在)。因此在这种情况下不等式有可能不成立，于是我们特判一下是否同时存在
。
倘若
中任意一个等于这个非
中两个数都是
倘若
倘若
所以说：取三个数的做法就是：首先特判一下是否存在 都为
的因子，这种情况下对于答案取一个
，使得情况如果存在就被考虑。 接下来取
， 然后删去所有
的因子（要取
的话，
的因子一定不出现在最后答案里面）
接下来就变成了取两个数的情况。
在剩下的数里面仍然取 ， 按照两个数的做法做即可。
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，一个没有
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！
活动奖励：
在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）
本道题目1月4日中午12：00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
投递牛客等公司