CF1814D Balancing Weapons 题解

KingPowers · 2023-11-03 16:32:37 · 题解

题目链接

首先不难发现一定有解，且答案上界显然为 n。具体地，令 F=\prod_{i=1}^nf_i，则我们将每个 d_i 调整为 \frac{F}{f_i} 即可使所有的 p_i 相等，也就是将每个 p_i 调整到每个 f_i 的公倍数。

所以我们只需要考虑答案不超过 n 的情况，注意到此时一定会有一把枪的 p_i 不变，考虑去枚举一个不变的 p_i，那么为了使极差不超过 k，其他枪最终的攻击力 p_j 都要尽可能地“接近”我们钦定不变的那个 p_i。

不难发现此时对于其它的每把枪，p_j 只会调整为以下值：

• 不变，也就是仍为 p_j。

• 变为不超过 p_i 且为 f_j 倍数的最大值。

• 变为超过 p_i 且为 f_j 倍数的最小值。

显然调整为其他值都不如以上三者之一更优，因此每把枪可能的取值数量之和是 O(n) 的。

考虑把这些取值全都拉出来排序，双指针扫描所有极差不超过 k 的极大区间，如果某个极大区间内的所有取值包含的枪的种类数为 n，那么就说明此时 n 把枪都有一个合法的取值，可以更新答案。

时间复杂度 O(n^2\log n)，比较卡常。

提交记录