ABC457D 题解

wyyinput · 2026-05-10 08:32:01 · 题解

二分答案是显然的。令二分的值为 P。

之后我们计算我们需要的代价，即 \sum \limits _{i=1}^N \max(0,\lceil \frac{P-A_i}{i} \rceil)。然后检查一下代价是否小于等于 K 就做完了。

可以证明答案在 long long 范围以内，因为考虑 N = 2 \times 10^5, A_i = 10^{18}, K = 10^{18} 时，令对 A_1 进行 X 次操作，则 A_1 = 10^{18} + X，这是一定小于等于 2 \times 10^{18} 的，因此使用 __int128 是完全没有必要的。

记录。没放赛时的提交是因为赛时代码有一处使用了 __int128，且二分的右界设置得较为粗糙。