欢迎光临散文网 会员登陆 & 注册

复盘|第316场周赛

2022-11-11 20:30 作者:UCLmsc  | 我要投稿

6214. 判断两个事件是否存在冲突

【模拟】无序将字符串转换为时间,直接比较字符串即可。

6224. 最大公因数等于 K 的子数组数目

【枚举】数据范围小直接暴力,加一点优化,如果nums[i]不是k的倍数就continue。

【优化枚举】去掉大量重复的GCD,需要记录gcd和范围右端点,需用到原地去重的操作。

6216. 使数组相等的最小开销

【枚举】nums和cost绑在一起排序,从小到大枚举nums[i],让所有数字都等于nums[i]。从nums[1]和nums[0]开始,total_cost增加(nums[1] - nums[0]) * cost[0]。 total_cost减少(sm_cost - cost[0]) * (nums[1] - nums[0])。总共减少(sm_cost - 2 * cost[0]) * (nums[1] - nums[0])

【中位数贪心】把cost[i]看作nums[i]的出现次数。可以证明把所有数变成中位数是最优解,排序之后不断累加cost[i],首次累加到≥⌈sumCost/2⌉就找到了中位数。

6217. 使数组相似的最少操作次数

【贪心】+-2无法改变奇偶,所以奇偶排序分组后,对应计算每个部分的正数和,//2就是答案。用排序区分奇偶。

由于元素都是正数,也可以把奇数编程相反数,排序后奇偶自动分开。


复盘|第316场周赛的评论 (共 条)

分享到微博请遵守国家法律