题意
给定 \(n\) 个数 \(a_1, a_2, \cdots, a_n\)，每次操作可以给其中的一个数加上 \(2\) 的非负整数次幂。求最小的操作次数，使得这 \(n\) 个数相等。
题解
首先考虑如何计算操作次数，设 \(maxa = \max\limits_{i = 1}^{n} a_i\)，如果我们把这 \(n\) 个数操作成了数 \(x\)（\(x \ge maxa\)），那么一共需要的操作次数为 \(\sum\limits_{i = 1}^{n} \operatorname{popcount\left(x - a_i\right)}\)。我们设 \(\Delta = x - maxa, b_i = maxa - a_i\)，那么需要的操作次数为 \(\sum\limits_{i = 1}^{n} \operatorname{popcount\left(\Delta + b_i\right)}\)。这样我们就可以把问题转化为求出一个 \(\Delta\)，最小化 \(\sum\limits_{i = 1}^{n} \operatorname{popcount\left(\Delta + b_i\right)}\)。
因为涉及到了位运算，我们考虑从低到高按位决策 \(\Delta\) 的值，影响第 \(i\) 位操作次数的因素有三：
- \(\Delta\) 在第 \(i\) 位的取值；
- \(b_k\) 在第 \(i\) 位的取值；
- \(b_k + \Delta\) 在第 \(i - 1\) 位是否会产生进位。
发现二进制下在第 \(i\) 位越容易进位的数在模 \(2^i\) 下越大，所以再处理每一位的时候可以先将 \(b_i\) 按模 \(2^i\) 的值降序排序，这样的话如果有 \(j\) 个数进位，那么一定是排序后的前 \(j\) 个数。
这样我们就可以设计出状态了。设 \(f_{i, j}\) 表示在二进制表示下有 \(j\) 个数进位到了第 \(i\) 位时的最优解。
接下来考虑转移，发现我们只需要处理当前二进制下第 \(i\) 位是否为 \(1\)和在第 \(i - 1\) 位进位的数个数 \(j\)。那么一共有 \(4\) 种数。接下来的讨论钦定上一位有 \(j\) 个数进位。
令 \(allCount\) 为这一位下为 \(1\) 的 \(b_k\) 的个数，\(nowCount\) 为这一位下为 \(1\) 且 \(k \le j\) 的 \(b_k\) 的个数。
- \(b_k + \Delta\) 在第 \(i - 1\) 位产生进位且 \(b_k\) 的第 \(i\) 位为 \(1\)，有 \(nowCount\) 个。
- \(b_k + \Delta\) 在第 \(i - 1\) 位产生进位且 \(b_k\) 的第 \(i\) 位为 \(0\)，有 \(j - nowCount\) 个。
- \(b_k + \Delta\) 在第 \(i - 1\) 位没有进位且 \(b_k\) 的第 \(i\) 位为 \(1\)，有 \(allCount - nowCount\) 个。
- \(b_k + \Delta\) 在第 \(i - 1\) 位没有进位且 \(b_k\) 的第 \(i\) 位为 \(0\)，有 \(n - j - \left(allCount - nowCount\right)\) 个。
那么我们考虑 \(\Delta\) 在第 \(i\) 位如何决策。
- 如果 \(\Delta\) 取 \(1\)，那么第 \(1, 2, 3\) 种数会产生进位，第 \(1, 4\) 种数的 \(\Delta + b_k\) 这一位是 \(1\)，需要进行操作。
- 如果 \(\Delta\) 取 \(0\)，那么第 \(1\) 种数会产生进位，第 \(2, 3\) 种数的 \(\Delta + b_k\) 这一位是 \(1\)，需要进行操作。
所以我们可以得出转移式：
\[\begin{aligned}f_{i + 1, allCount - nowCount + j} &= \min{f_{i, j} + nowCount + \left(n - j\right) - \left(allCount - nowCount\right)} \\ f_{i + 1, nowCount} &= \min{f_{i, j} + j - nowCount + allCount - nowCount}\end{aligned}\]至此我们就可以以 \(\mathcal{O}(n \log n \log a)\) 的复杂度通过本题。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
constexpr valueType maxB = 58;
constexpr valueType MIN = LONG_LONG_MIN >> 8, MAX = LONG_LONG_MAX >> 8;
typedef std::array<valueType, maxB> BitArray;
typedef std::bitset<maxB> bitset;
typedef std::vector<bitset> BitsetVector;
valueType popcount(valueType x) {
return __builtin_popcountll(x);
}
constexpr std::array<valueType, maxB> bin = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 31072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 5184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872};
class ModCompare {
private:
valueType mod;
public:
explicit ModCompare(valueType mod) : mod(mod) {}
bool operator()(valueType a, valueType b) const {
return a % mod > b % mod;
}
void setMod(valueType m) {
mod = m;
}
};
int main() {
std::ios::sync_with_stdio(false);
valueType N;
std::cin >> N;
ValueVector source(N);
for (auto &iter: source)
std::cin >> iter;
valueType const maxNumber = *std::max_element(source.begin(), source.end());
for (auto &iter: source)
iter = maxNumber - iter;
BitArray bitCount;
for (valueType i = 0; i < maxB; ++i)
for (auto const &iter: source)
if (iter & bin[i])
++bitCount[i];
ValueMatrix dp(maxB, ValueVector(N + 1, MAX));
dp[0][0] = 0;
for (valueType i = 0; i < maxB - 1; ++i) {
if (i > 0)
std::sort(source.begin(), source.end(), ModCompare(bin[i]));
valueType allCount = 0, nowCount = 0;
for (auto const &iter: source)
if (iter & bin[i])
++allCount;
for (valueType j = 0; j <= N; ++j) {
if (j > 0 && source[j - 1] & bin[i])
++nowCount;
dp[i + 1][allCount - nowCount + j] = std::min(dp[i + 1][allCount - nowCount + j], dp[i][j] + nowCount + (N - j) - (allCount - nowCount));
dp[i + 1][nowCount] = std::min(dp[i + 1][nowCount], dp[i][j] + j - nowCount + allCount - nowCount);
}
}
std::cout << dp[maxB - 1][0] << std::endl;
return 0;
}