- 给定 $n$ 个数字 $a_1,a_2,\cdots,a_n$，每次操作可以给某个 $a_i$ 加上 $2$ 的非负整数次幂。
- 求最少的操作次数使得 $n$ 个数相等。
- $1\leq n\leq 10^5,0\leq a_i\leq 10^{17}$
sol
- 不妨先将 $a$ 从小到大排序。
- 设最后每个数都等于 $a_n+x(x\geq 0)$。那么总代价为 $\sum\limits_{i=1}^n popcount(a_n+x-a_i)$。
- 现在要找一个 $x$ 使得答案最小。不妨先将 $a_i$ 变为原先的 $a_n-a_i$。
-
那么现在总代价为 $\sum\limits_{i=1}^n popcount(x+a_i)$。
-
从低到高考虑每一位，那么 $x+a_i$ 的第 $k$ 位是 $0/1$ 由以下三个条件决定：
- $x$ 的第 $k$ 位是 $0$ 还是 $1$
- $a_i$ 的第 $k$ 位是 $0$ 还是 $1$
- $x+a_i$ 的第 $k-1$ 位有没有向前进位
- 暴力的做法是从低到高枚举每一位，用 $2^n$ 的状态记录每个数有没有进位，显然复杂度接受不了。
- 但是可以发现，由于每个 $a_i$ 加的都是 $x$，所以 $a_i$ 的后 $k-1$ 位越大，越可能向第 $k$ 位进位。
-
所以，“每个数有没有进位”的状态数只有 $O(n)$ 个，每个进位状态为后 $k-1$ 位从小到大排序后的一个后缀。
-
记 $f[k][i]$ 表示考虑了后 $k$ 位，后 $k$ 位最大的 $i$ 个数进位的最小代价。
- 如何转移？考虑当前这一位 $x$ 是 $0$ 还是 $1$。
- 0：
- 对答案的贡献：“前一位没进位且第 $k$ 位为 $1$ 的数“的个数 + ”前一位进位且第 $k$ 位为 $0$ 的数“的个数（$x+a_i$ 在这一位为 $1$）；
- 进位的数量："前一位进位且第 $k$ 位为 $1$ 的数"的个数。
- 1：
- 对答案的贡献：“前一位进位且第 $k$ 位为 $1$ 的数“的个数 + ”前一位没进位且第 $k$ 位为 $0$ 的数“的个数（$x+a_i$ 在这一位为 $1$）；
-
进位的数量：$n-$"前一位没进位且第 $k$ 位为 $0$ 的数"的个数。
-
至于如何求这些“个数”，就记个前缀和，存下后 $k$ 位从小到大前 $i$ 个中没进位数的个数和进位的数的个数即可。
- 可以用类似于基数排序的方法优化每次的排序，时间复杂度 $O(n \log V)$，其中 $V=\max{a_i}$。
```cpp
include
include
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
int n,p[510000],sum[2][510000];
int tmp1[510000],tmp2[510000];
ll dp[60][510000],c1,c2,c3,p1,p2,m;
ll sta,a[510000];
/bool cmp(int x,int y){
return (a[x]&sta)<(a[y]&sta);
}/
int main(){
// freopen("equal.in","r",stdin);
// freopen("equal.out","w",stdout);
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];
for (int w=0;w<=58;w++)
for (int i=0;i<=n;i++)
dp[w][i]=INF;
for (int i=1;i<=n;i++) p[i]=i;
dp[0][0]=0;
for (int w=0;w<58;w++){
sta=(1ll<<w)-1;
// sort(p+1,p+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[p[i]]>>w)&1][i]++;
}
for (int i=0;i<=n;i++){
int tmp=(sum[0][n]-sum[0][n-i])+sum[1][n-i];
int sta=sum[1][n]-sum[1][n-i];
dp[w+1][sta]=min(dp[w+1][sta],dp[w][i]+tmp);
}
for (int i=0;i<=n;i++){
int tmp=(sum[1][n]-sum[1][n-i])+sum[0][n-i];
int sta=n-sum[0][n-i];
dp[w+1][sta]=min(dp[w+1][sta],dp[w][i]+tmp);
}
int cnt1=0,cnt2=0;
for (int i=1;i<=n;i++)
if ((a[p[i]]>>w)&1) tmp1[++cnt1]=p[i];
else tmp2[++cnt2]=p[i];
int k=0;
for (int i=1;i<=cnt2;i++) p[++k]=tmp2[i];
for (int i=1;i<=cnt1;i++) p[++k]=tmp1[i];
}
printf("%lld\n",dp[58][0]);
return 0;
}
```