CF1188D Make Equal

假设 \(a\) 数组有序，记 \(\text{cnt}(x)\) 表示 \(x\) 的二进制表示中 \(1\) 的个数。
那么我们就是要找一个 \(x\) 使得 \(\sum_{i=1}^{n}\text{cnt}(x+a_n-a_i)\) 最小。下面令 \(a_i\gets a_n-a_i\)。
我们考虑 \(x+a_i\) 的第 \(k\) 位。这一位的决策与下面的东西有关：

• \(x\) 这一位填不填 \(1\)（要决策的东西）
• \(a_i\) 这一位是不是 \(1\)
• 前一位的进位情况

棘手的是第三种情况，如果暴力记录，有 \(2^n\) 种情况。但是注意到，由于 \(x\) 是相同的，那么 \(a_i\) 前 \(k-1\) 位越大越容易进位。如果将所有 \(a_i\) 按照 \(a_i\bmod 2^k\) 的大小从大到小排序，则最后进位的一定是一段前缀，那么就可以 DP 了。
设 \(f_{i,j}\) 表示前 \(i\) 位，有 \(j\) 个数进位。转移有如下四种情况：

• \(x+a_k\) 在第 \(i\) 位没有进位，\(a_k\) 的 \(i+1\) 位为 \(1\)。
• \(x+a_k\) 在第 \(i\) 位没有进位，\(a_k\) 的 \(i+1\) 位为 \(0\)。
• \(x+a_k\) 在第 \(i\) 位进位，\(a_k\) 的 \(i+1\) 位为 \(1\)。
• \(x+a_k\) 在第 \(i\) 位进位，\(a_k\) 的 \(i+1\) 位为 \(0\)。

枚举 \(x\) 的第 \(i+1\) 位：

• 该位为 \(1\)，第一、三、四种会进位，第二、三类 \(i+1\) 位为 \(1\)。
• 该位为 \(0\)，第三类会进位，第一、四类 \(i+1\) 位为 \(1\)。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n;
ll a[N];
int f[62][N];
int id[N];
int K;
int sum[2][N];

bool cmp(int x, int y) {
	return (a[x] & ((1ll << K) - 1)) < (a[y] & ((1ll << K) - 1));
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) a[i] = a[n] - a[i], id[i] = i;
	memset(f, 0x3f, sizeof f); f[0][0] = 0;
	for (int k = 0; k <= 60; ++k) {
		K = k;
		sort(id + 1, id + n + 1, cmp);
		for (int i = 1; i <= n; ++i) {
			sum[0][i] = sum[0][i - 1],
			sum[1][i] = sum[1][i - 1];
			++sum[a[id[i]] >> k & 1][i];
		}
		for (int i = 0; i <= n; ++i) {
			int x, y;
			x = sum[1][n - i] + sum[0][n] - sum[0][n - i], y = sum[1][n] - sum[1][n - i];
			f[k + 1][y] = min(f[k + 1][y], f[k][i] + x);
			x = sum[0][n - i] + sum[1][n] - sum[1][n - i], y = n - sum[0][n - i];
			f[k + 1][y] = min(f[k + 1][y], f[k][i] + x);
		}
	}
	printf("%d", f[61][0]);
	return 0;
}