【⭐】ABC 424E

对只含有一个整数 $x$ 的序列，至少需要执行多少次操作才能使得序列中的所有元素不大于某个值 $d$？此时序列中的元素数量与值分别是什么？

在提示一的基础上，考虑对一列整数 $a_1,a_2,\cdots ,a_n$，至少需要执行多少次操作才能使得序列中的所有元素不大于某个值 $d$？

在提示二的基础上，考虑对一列整数 $a_1,a_2,\cdots ,a_n$，执行 $k$ 次操作后序列中的最大元素的值为多少？

在整个过程中序列最多可能存在多少种不同的值？

提示一的答案：至少需要执行 $2^k-1$ 次操作，其中 $k$ 满足 $2^k\times d\ge x$ 的最小整数。序列中此时有 $2^k$ 个元素，每个元素的值均为 ${\displaystyle \frac{x}{2^k}}$。

提示二的答案：$\sum _{i=1}^n(2^{k_i}-1)$，其中 $k_i$ 是满足 $2^{k_i}\times d\ge a_i$ 的最小整数。

提示三的答案：二分该最大元素，设其为 $d$，考察提示二的问题的答案与 $k$ 的关系。

提示四的答案：$n+1$。手动模拟上述操作的过程很容易证明该性质成立。

基于上述内容，我们首先解出 $k$ 次操作后的最大元素，设其为 $m$。随后手动枚举序列中可能存在的 $n+1$ 中元素及其数目即可得到答案。

为了避免使用小数导致运算过程中可能出现的误差，我们可以在输入 $a_i$ 后令 $a_i\leftarrow 2^{30}\times a_i$，基于提示一可以证明在整个运算过程中不会出现小数。不过输出时注意除掉一开始乘上去的 $2^{30}$，以及要跟着样例输出开 setprecision(15)，不然输出精度不够（因为这个多调了一个小时的心酸泪）。

基于提示四可以得出另一种更加直白的解法：使用优先队列直接模拟所有的 $k$ 次操作。依据提示一、二，我们可以得知序列中的每个数最多会被减半 $\mathcal{O}(\log k)$ 次，因此我们可以在 $\mathcal{O}(n\log k\log n)$ 的时间复杂度内解决问题。