题目大意
给出 \(n\) 个数字 \(a_1,a_2,\dots,a_n\)，每次操作可以给其中一个数加上 \(2\) 的非负整数次幂。求最少的操作次数，使得这 \(n\) 个数相等。
思路
记 \(b_i = \max\limits_{1 \leq k \leq n}{a_k} - a_i\)，这道题的目的是求一个值 \(x\) 使得
\[\sum_{i=1}^n \operatorname{popcount}(x + b_i) \]最小，其中 \(\operatorname{popcount}(x)\) 表示数 \(x\) 在二进制下 \(1\) 的个数。
考虑 DP。
考虑二进制下 \(x + b_i\) 的第 \(k\) 位，发现这一位的决策与下面这些有关：
- \(x\) 的第 \(k\) 位是否填 \(1\)；
- \(b_i\) 的第 \(k\) 位是否为 \(1\)；
- 第 \(k-1\) 位是否进位。
其中，\(x\) 是我们要决策的，\(b_i\) 是已知的，考虑第三种情况。
如果直接进行记录的话很明显要爆炸。但我们发现，第 \(k-1\) 位的进位情况与 \(b_i \mod 2^k\) 有关。
\(b_i \mod 2^k\) 的值越大，就更加容易进位，如果将 \(b_i\) 按照 \(b_i \mod 2^k\) 的值从大到小排序，能产生进位的数一定是 \(b_i\) 的一段前缀。
设 \(dp_{i,j}\) 表示有 \(j\) 个数进位到第 \(i\) 位的最优解（最小操作次数）。
考虑转移，对于第 \(i\) 位，我们要考虑 \(b_k\) 在二进制下第 \(i\) 位是否为 \(1\) 和在第 \(i-1\) 位进位的数的个数。
钦定第 \(i - 1\) 位有 \(j\) 个数进位，记 \(tot\) 为当前这一位为 \(1\) 的 \(b_k\) 的个数；\(cnt\) 为前 \(j\) 个数中当前这一位为 \(1\) 的数的个数。
考虑下面四种情况，表示满足前面两句条件的数有多少个：
- \(x+b_k\) 在第 \(i-1\) 位没有进位，\(b_k\) 的第 \(i\) 位为 \(1\)，有 \(tot-cnt\) 个；
- \(x+b_k\) 在第 \(i-1\) 位没有进位，\(b_k\) 的第 \(i\) 位为 \(0\)，有 \(n-j-(tot-cnt)\) 个；
- \(x+b_k\) 在第 \(i-1\) 位有进位，\(b_k\) 的第 \(i\) 位为 \(1\)，有 \(cnt\) 个；
- \(x+b_k\) 在第 \(i-1\) 位有进位，\(b_k\) 的第 \(i\) 位为 \(0\)，有 \(j-cnt\) 个。
那么考虑第 \(i\) 位的决策：
- 如果 \(x\) 取 \(0\)，那么第 \(3\) 种产生进位，第 \(1,4\) 种的 \(x+b_k\) 的第 \(i\) 位为 \(1\)，产生贡献；
- 如果 \(x\) 取 \(1\)，那么第 \(1,3,4\) 种产生进位，第 \(2,3\) 种的 \(x+b_k\) 的第 \(i\) 位为 \(1\)，产生贡献；
然后就可以进行转移。
标签：cnt,Make,个数,Equal,tot,CF1188D,考虑,进位,位为 From： https://www.cnblogs.com/baijian0212/p/solution-cf1188d.html