題解
将 \(a_1,a_2,\dots,a_n\) 從小到大排序，若 \(a_n\) 加上了 \(x\)，顯然讓所有數最終都等于 \(a_n+x\) 是最優的。
是以就是求 \(\sum_{i=1}^n \operatorname{popcount}(x+a_n-a_i)\) 的最小值。
對于所有 \(i\)，令 \(a_i\gets a_n-a_i\)。
我們發現，當一個位 \(k\)，數 \(a_i\) 滿足如下三個條件中的至少兩個時，它就會産生進位:
- \(a_i\) 的第 \(k\) 位為 \(1\)；
- \(a_i\) 的第 \(k-1\) 位産生了進位；
- \(x\) 的第 \(k\) 位為 \(1\)。
對于每個位 \(k\)，按照 \(a_i\bmod 2^{k+1}\) 從大到小排序，并記該數組為 \(b_{k}\)，那麼能産生進位的數是 \(b_k\) 的一個字首。
設 \(f_{i,j}\) 為考慮最低的 \(i\) 位，第 \(i\) 位有 \(j\) 個數産生進位的最小答案。
記 \(cnt_{i,j}\) 為 \(b_i\) 的前 \(j\) 個元素中，有多少個元素的第 \(i+1\) 位為 \(1\)，\(l_i\) 為 \(\sum_{j=1}^n [a_j\operatorname{and} 2^i=2^i]\)。分類讨論 \(x\) 的第 \(i\) 位：
-
\(x \operatorname{and} 2^i=1\)：
\[f_{i,j}=\min_{cnt_{i-1,k}=j}\{f_{i-1,k}+k\}+l_i-2j\\\forall 1\le i\le \log V+1,1\le j\le l_i
\]
-
\(x \operatorname{and} 2^i=0\)：
\[f_{i,j}=\min_{l_i+k-cnt_{i-1,k}=j}\{f_{i-1,k}+cnt_{i-1,k}+(n-l_i)-(k-cnt_{i-1,k})\}\\\forall 1\le i\le \log V+1,l_i\le j\le n
代碼
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T>
void Read(T &_x){
_x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
_x*=_f;
}
template<typename T,typename... Args>
void Read(T &_x,Args& ...others){
Read(_x);Read(others...);
}
typedef long long ll;
const int N=1e5+5,LogV=59;
int n,id[LogV][N],f[LogV][N],l[LogV],cnt[LogV][N],g1[N],g2[N];
ll a[N],num[LogV][N];
void Store(int _i,int _j){
g1[cnt[_i][_j]]=min(g1[cnt[_i][_j]],f[_i][_j]+_j);
g2[_j-cnt[_i][_j]]=min(g2[_j-cnt[_i][_j]],f[_i][_j]+2*cnt[_i][_j]-_j);
}
int main(){
Read(n);
For(i,1,n) Read(a[i]);
sort(a+1,a+n+1);
For(i,1,n){
a[i]=a[n]-a[i];
for(ll j=0,cur=a[i]&1;j<LogV;++j,cur=cur|(a[i]&(1LL<<j))){
id[j][i]=i,num[j][i]=cur;
}
}
For(j,0,LogV-1){
sort(id[j]+1,id[j]+n+1,[j](int x,int y){return num[j][x]>num[j][y];});
For(i,1,n){
l[j]+=bool(a[i]&(1LL<<j));
cnt[j][i]=cnt[j][i-1]+bool(a[id[j][i]]&(1LL<<(j+1)));
}
}
memset(f,0x3f,sizeof f);
memset(g1,0x3f,sizeof g1);
memset(g2,0x3f,sizeof g2);
f[0][0]=l[0],f[0][l[0]]=min(f[0][l[0]],n-l[0]);
Store(0,0),Store(0,l[0]);
For(i,1,LogV-1){
For(j,0,l[i]){
f[i][j]=g1[j]+l[i]-2*j;
}
For(j,l[i],n){
f[i][j]=min(f[i][j],g2[j-l[i]]+n-l[i]);
}
memset(g1,0x3f,sizeof g1);
memset(g2,0x3f,sizeof g2);
For(j,0,n){
Store(i,j);
}
}
printf("%d\n",f[LogV-1][0]);
return 0;
}
Written by Alan_Zhao