题解

思路

设 $M=\max a_i$，最终公共值写成 $M+t$。把 $b_i=M-a_i$，则把 $a_i$ 增加到公共值的最少操作数是 $\operatorname{popcount}(t+b_i)$。问题等价于

$$\min_{t\ge0}\sum_{i=1}^{n}\operatorname{popcount}(t+b_i).$$

存在最优解满足 $t\le\max b_i$，因此只需考虑有限位二进制数。

做法

子任务 1：枚举公共值偏移

枚举 $0\le t\le\max b_i$，直接计算所有 $t+b_i$ 的二进制一的个数之和。时间复杂度为 $O(n(\max a_i-\min a_i))$。

子任务 2：两个数的数位动态规划

当 $n=2$ 时，只有 $b_1=0,b_2=d$。从低位到高位枚举 $t$ 的当前位，状态只需记录 $t+d$ 向当前位传来的进位。转移代价是 $t$ 当前位与 $t+d$ 当前位的一的个数，状态数为常数。

子任务 3：进位后缀动态规划

逐位决定 $t$。处理第 $k$ 位前，只看每个 $b_i$ 的低 $k$ 位。若按 $b_i\bmod2^k$ 排序，那么加上同一个 $t\bmod2^k$ 后，产生进位的元素一定构成一个后缀。因此状态只需记录这个后缀的长度 $s$。

设 $dp[k][s]$ 表示已经决定 $t$ 的前 $k$ 位、恰有排序后末尾 $s$ 个数向第 $k$ 位进位时，已经产生的最小一位数总和。

尝试令 $t$ 的第 $k$ 位为 $0$ 或 $1$。预处理当前排序中第 $k$ 位为零和为一的前缀数量，即可在 $O(1)$ 时间算出：

• 当前所有 $t+b_i$ 在第 $k$ 位产生多少个一；
• 下一位产生进位的元素数量。

每处理完一位，用当前位对下标作稳定的零一分组，即得到按低一位更长余数排序的次序。处理足够多的高位后要求最终进位数为零。

正确性证明

引理 1

固定公共值 $M+t$ 时，最少操作数为 $\sum_i\operatorname{popcount}(t+b_i)$。

证明。 每次操作增加一个二的幂。把差值写成若干二的幂所需的最少项数，正是其二进制表示中一的个数；不同元素之间的操作互不影响。$\square$

引理 2

处理低 $k$ 位时，产生向第 $k$ 位进位的 $b_i$ 在按 $b_i\bmod2^k$ 排序后构成一个后缀。

证明。 产生进位当且仅当 $(b_i\bmod2^k)+(t\bmod2^k)\ge2^k$。右侧阈值固定，所有达到阈值的余数恰为排序后的一个后缀。$\square$

引理 3

状态 $(k,s)$ 包含决定下一位所需的全部信息。

证明。 由引理 2，$s$ 唯一确定哪些元素带进位。结合这些元素的 $b_i$ 第 $k$ 位和候选的 $t$ 第 $k$ 位，可以唯一确定每个和的当前位以及下一位进位；更低位不再影响后续。$\square$

定理

进位后缀动态规划得到最少操作次数。

证明。 由引理 1，目标是最小化所有二进制一的总数。动态规划枚举 $t$ 的每一位；由引理 3，转移既无遗漏也无重复，并精确累计当前位代价。最终无进位状态覆盖所有有限非负 $t$，取最小值即全局最优。$\square$

复杂度

设有效二进制位数为 $F=63$。满分算法时间复杂度为 $O(nF)$，空间复杂度为 $O(nF)$。