题号 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
- 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
(4) 回帖