CF2255D 题解

前言

是啊，我觉得我打 oi 的时候会做这个题，

思路

正难则反，从最后全 $0$ 的状态往前做。

考虑每个时刻 $a_i$ 最大是多少（上界）。对于一个能在 $t$ 次操作后被清零的数组 $a_i$，任意一个满足 $b_i\leq a_i$ 的数组 $b$ 也可以在 $t$ 次操作后被清零。

在第 $t$ 个时刻，对于这一次被选中的下标 $i$，$a_i$ 的上界可以是 $2a_i\color{red}+1$，而对于没有选中的下标 $j$，其上界则会变为 $2a_j$。

如果答案为 $T$，那么在第 $t$ 个时刻选中 $a_i$，相当于给最终 $a_i$ 的上界加上了 $2^{T-t}$。

固定答案 $T$ 后，问题的形式变成：你现在有 $S=2^0,2^1,2^2,\cdots,2^{T-1}$，每次你可以选定一个下标 $i$，将其中的一个数字 $x\in S$ 分配给 $a_i$，让 $a_i\leftarrow a_i+x$，并从 $S$ 里删去 $x$。

可以采用贪心策略来解决这个问题。从大到小枚举 $2$ 的幂次 $2^k$ 分配给当前 $a$ 中最大的元素 $a_i$，令 $a_i\leftarrow a_i-2^k$ 即可。容易证明其正确性。

在实现上，先二分答案 $T\in [n,n+\log V+1]$。我们可以用很低的复杂度来 check：对于所有 $k>\log V$，$2^k$ 都可以直接消灭一个元素，前 $w=\max(T-(\log V+1),0)$ 大的元素都会直接被消灭。因此只需要取前 $n-w$ 小的元素出来做即可。

复杂度 $\mathcal{O}(n\log n)$，瓶颈在排序。