IncrementAndDoubling

作者：马龙

关键词：贪心 倍增

题目简述

你有一个包含$n$个元素的序列，初始时所有元素均为$0$。你可以执行若干次操作，每次操作是下列两种当中的某一种：

• 增量操作：给某个元素加$1$。
• 倍增操作：将序列中所有的元素乘以$2$。

给定这个序列的最终状态，求至少操作多少次才能到达这个状态。

$n \leq 50$，最终每个元素的值$v$是$[0, 1000]$中的整数

分析

先来考虑$n=1$时的情况。我们将这个数写成二进制形式，不难发现，假如有$x$个位上为$1$，那么我们至少要执行$x$次增量操作，因为增量操作至多会使$1$的数量增加$1$，而倍增操作不会影响$1$的数量。而也确实存在一个只执行$x$次增量操作的策略：我们可以从高位向低位构造这个数，由第$i$位构造到第$i+1$位的时候，先执行一次左移，然后假如第$i+1$位为$1$，那么就再执行一次增量操作。不难发现，对于单个数而言，这个策略是最优的。

考虑如何将这一策略扩展到多个数的情况。由于单次增量操作只会影响一个数，我们只需要考虑倍增操作。可以发现，所有的数可以共享相同的倍增操作，从而使得总操作数等于最大数所需的操作数；显然不会有策略比这更好了。而假如有某些数不需要这么多倍增操作，我们可以通过推迟增量操作来延后它受倍增操作影响的时间。由于每个数都是按照单个数时的最优策略来执行的，这个策略对于多个数而言也是最优的。

算法一

有了上述分析，不难知道，最优操作数等于最大数所需的倍增操作数，加上所有数的二进制表示中$1$的个数和。只需扫描所有的元素，做对应的计算即可。复杂度是$O(n \log v)$。