题解：CF2053D Refined Product Optimality

lgx57 · 2024-12-29 16:57:35 · 题解

有史以来最水的 D。

首先考虑不操作时怎样能使 P 最大，很明显是当 a 和 b 都升序排序的时候，由于 b 可以任意顺序排列，所以相当于可以任意匹配 a_i 和 b_j。

然后考虑修改后的情况。由于 op=1 与 op=2 的情况类似，所以下文只考虑 op=1 时的情况。

我们设 num=a_x，那么容易发现修改的一定是最靠后的数（因为这样对应的 b_i）比较大。于是二分出 num 最靠后的位置，设这个位置为 Ans，然后在模意义下除以 \min(a_{Ans},b_{Ans})，再乘上 \min(a_{Ans}+1,b_{Ans})，最后不要忘记 a_{Ans} \gets a_{Ans}+1。

代码很简单，这里不给了。注意实现二分时 Ans 的初始值为 n。