P10675 【MX-S1-T4】先见之明

如果这个 $2^j$ 是用一些 $\le 2^{p_{i+1}}$ 的 $a$ 凑成的，那么肯定经过了这些 $a$ 先加到 $2^{p_{i+1}+1}$ 再不断进位到 $2^j$，既然中间都存在到一个更小值的过程，那把 $j$ 换成 $p_{i+1} + 1$ 肯定更优，所以一种可能的取值是 $2^{p_{i+1} + 1}$。

如果 $2^j$ 用了 $> 2^{p_{i+1}}$ 的 $a$ 凑，那么这些 $a$ 肯定不会 $\le 2^{p_{i+1}}$，理由同上。那么肯定只用一个 $a$ 最优，且这个 $a$ 肯定是出现在 $[p_{i+1} + 1,p_{i} - 1]$ 中最小的那个，证明和上面类似：如果取的不是最小那个，那么这个最小的用途肯定是去凑 $\ge 2^{p_i}$ 的数了，中间肯定有个过程是变成了 $2^j$，那把这个 $2^j$ 用一开始就存在的这个 $2^j$ 替换掉肯定更优。

如果 $x=2^t$，那么只考虑 $\le t$ 的 $a_i$，条件就是 $\sum 2^{a_i} \ge x$。

如果 $x=\sum\limits_{i=1}^k 2^{b_i}(b_i < b_{i+1})$，那么条件就是 $\forall i,\sum\limits_{j\le i} 2^{b_j} \le \sum\limits_{a_j \le b_i} 2^{a_j}$，容易归纳证明。