Make Equal
题目大意
给出 \(n\) 个数字 \(a_1,a_2,a_3,......,a_n\),每次操作可以给其中一个数加上 \(2\) 的非负整数次幂。求最少的操作次数，使得这 \(n\) 个数相等。
思路
模拟赛看到这道题然后直接打的暴力拿了40分。暴力思路就是你需要找到一个大于等于 \(a_{max}\) 的 \(m\) 然后再每个值都向这个 \(m\) 加次数，最后枚举 \(a_{max}\) 后若干位（我是往后10000位）找到次数最小值即为答案，但是如果数据过大就骗不了分，只能拿40分。
放上40分考场代码：
const int N=1e5+1e4+5;
inline int qpow(int a,int x,int mod){
int res=1;
while(x){
if(x&1) res=res*a%mod;
x>>=1;
a=a*a%mod;
}
return res%mod;
}
int a[N],maxn=-1;
int n,Tempestissimo(LONG_LONG_MAX);
int two[25];
int baoli[N];
inline int _(int num){
int res=0;
while(num){
int t=log2(num);
num-=two[t];
res++;
}
return res;
}
inline int __(int nitian){
int res=0;
for(register int i=1;i<=n;i++){
res+=(baoli[nitian-a[i]]);
}
return res;
}
main(){
two[0]=1;
for(register int i=1;i<=20;i++){
two[i]=two[i-1]<<1;
}
n=read();
for(register int i=1;i<=n;i++){
a[i]=read();
maxn=max(maxn,a[i]);
}
for(register int i=1;i<=maxn+10000;i++){
baoli[i]=_(i);
}
for(register int i=maxn;i<=maxn+10000;i++){
Tempestissimo=min(Tempestissimo,__(i));
}
write(Tempestissimo);
return 0;
}
看过这个代码就会发现，我求每个数转移到其它数的方法是找 \(2\) 的幂从高位到低位找。但是实际上不用这么麻烦。
假设我们找到一个大于等于 \(a_{max}\) 的值 \(m\) ，那么任意一个数 \(a_i\) 改变到 \(m\) 的贡献次数显然是 \(popcount(m-a_i)\) 。比如说 \(101\) 转移到 \(111\) ，我们只需要加上 \(2^2\) 就行，那么只需要走 \(1\) 步就能转移过去。
对于 \(a_1,a_2,a_3,...,a_n\) 我们可以将答案表示出来为：
\[\sum_{i=1}^n{popcount(m-a_i)} \]这个时候 \(m\) 有大于 \(a_{max}\) 的限制，现在考虑去掉这个限制。
我们假设 \(\Delta\) 为 \(m-a_{max}\)，设 \(b_i\) 为 \(a_{max}-a_i\) 这样就能将答案转化为：
\[\sum_{i=1}^n{popcount(\Delta+b_i)} \]首先，我们要明确一点，我们要求的答案是某一位上 \(\Delta+b_i\) 是否为 \(1\)。
我们需要对于每一位上是否为 \(1\) 进行讨论，影响这一位上是否为 \(1\) 的因素有三个：
- \(\Delta\) 这一位上的取值。
- \(b_i\) 这一位上的取值。
- \(\Delta+b_i\) 在 \(i-1\) 位上是否进位到第 \(i\) 位上。
发现对于前 \(k\) 位来说，二进制下容易产生进位的数在模 \(2^k\) 意义下更大。
举个例子来说：\(10000\) 和 \(01111\)，前者更容易产生进位，因为只要在第五位上加入一个 \(1\) 就能进位了，但是后者需要在第五位上加入两个 \(1\) 才能进位。
那么如果说有 \(j\) 个数产生进位，那么一定是模 \(2^k\) 意义下更大的数进位。
Q: 你怎么能说只有模 \(2^k\) 意义下更大的数才能进位，那我选一个小的数难道不行吗？
A: 因为题目是求最少的操作次数，能加一个 \(1\) 就转移走肯定比加两个 \(1\) 转移走的更优，所以我们要选模 \(2^k\) 意义下更大的 \(j\) 个数。
设计转移方程：\(dp_{i,j}\) 表示在前 \(i\) 位中，有 \(j\) 个数在 \(i-1\) 到 \(i\)的时候产生进位的最优解步数。
将 \(b_i\) 数组按照前 \(k\) 位升序排序之后，这个数组的后 \(j\) 位就是产生进位的数。
假设 \(nowcount\) 为 \(b\) 数组中后 \(j\) 位中 \(1\) 的数量，\(allcount\) 为 \(b\) 数组中 \(1\) 的数量。我们现在需要确定的条件有三个，一是 \(b_i\)，二是\(\text{进位}\)，三是 \(\Delta\)。 先考虑前两个条件，在第 \(i\) 位，分为下面四类情况讨论：
-
\(1.\) \(b_i+\Delta\) 在第 \(i-1\) 位向第 \(i\) 位有进位，且 \(b_i\) 这一位上是 \(1\) ，总共有 \(nowcount\) 种可能。
-
\(2.\) \(b_i+\Delta\) 在第 \(i-1\) 位向第 \(i\) 位有进位，且 \(b_i\) 这一位上是 \(0\) ，总共有 \(j-nowcount\) 种可能。
-
\(3.\) \(b_i+\Delta\) 在第 \(i-1\) 位向第 \(i\) 位没有进位，且 \(b_i\) 这一位上是 \(1\) ，总共有 \(allcount-nowcount\) 种可能。
-
\(4.\) \(b_i+\Delta\) 在第 \(i-1\) 位向第 \(i\) 位没有进位，且 \(b_i\) 这一位上是 \(0\) ，总共有 \(n-j+nowcount-allcount\) 种可能。
解释一下第一个：\(nowcount\) 是后 \(j\) 位中 \(1\) 的数量，只有后 \(j\) 位才有进位，所以满足有进位并且这一位上是 \(1\) ，总共 \(nowcount\) 种可能。
解释一下第二个：只有后 \(j\) 位才有进位，用总共进了 \(j\) 位减去 \(b_i\) 后 \(j\) 位 \(1\) 的数量，就是进位并且 \(b_i\) 为 \(0\) 的情况，所以总共 \(j-nowcount\) 中可能。
解释一下第三个：\(allcount-nowcount\) 求出的是不是后 \(j\) 位（即不进位）中 \(1\) 的数量。
解释一下第四个：总共 \(n\) 种情况（即 \(1-n\) 中 \(0\) 的个数加上 \(1\) 的个数），减去前三个就是第四个 \(n-j+nowcount-allcount\)。
上面是解决了前两个条件 \(b_i\) 和 \(\text{进位}\)，还剩下一个条件：\(\Delta\)。
我们要明确一点，我们要求的答案是某一位上 \(\Delta+b_i\) 是否为 \(1\) 的贡献，而不是 \(b_i\) 从 \(0\) 变成 \(b_i+\Delta\) 的 \(1\) 的贡献。因为要求转移方程，我们还需要记录每种情况进位多少。
根据这一位上的数是多少用式子： \(\text{进位}+b_i+\Delta\) 模 \(2\) 理解。
- \(\Delta=0\) 的时候：
第一种情况（\(1+1+0\)）产生进位，这一位上是 \(0\)，产生进位贡献。
第二种情况（\(1+0+0\)）不产生进位，这一位上是 \(1\)，产生步数贡献。
第三种情况（\(0+1+0\)）不产生进位，这一位上是 \(1\)，产生步数贡献。
第四种情况（\(0+0+0\)）不产生进位，这一位上是 \(0\)，不产生贡献。
- \(\Delta=1\) 的时候：
第一种情况（\(1+1+1\)）产生进位，这一位上是 \(1\)，产生进位贡献和步数贡献。
第二种情况（\(1+0+1\)）产生进位，这一位上是 \(0\)，产生进位贡献。
第三种情况（\(0+1+1\)）产生进位，这一位上是 \(0\)，产生进位贡献。
第四种情况（\(0+0+1\)）不产生进位，这一位上是 \(1\)，产生步数贡献。
只要理解了上面八种情况，想必很快就能做出来罢！
得出转移方程：
\[dp_{k+1,nowcount}=min(dp_{k,i}+i-nowcount+allcount-nowcount) \]\[dp_{k+1,i+allcount-nowcount}=min(dp_{k,i}+nowcount+n-i+nowcount-allcount) \]不会还有没看懂的罢， 左边第二维上是进位贡献，右边的是步数贡献。
我们可以使用前缀和来求 \(nowcount\) 和 \(allcount\)。
假设 \(sum_{i,j}\) 意思是在第 \(k\) 位的时候前 \(i\) 个数，\(b\)数组排完序之后第 \(i\) 个位置上是 \(1/0\) ，有多少个。
那么根据上文对 \(nowcount\) 的定义，\(nowcount=sum_{n,1}-sum_{n-i,0}\)
，其中 \(i\) 是不断枚举的进了几位，意义同上面转移方程。
根据上文对 \(allcount\) 的定义，\(allcount=sum_{n,1}\)。
进行 \(60\) 次位上运算之后，从第 \(60\) 位转移到第 \(61\) 位的 \(dp_{61,0}\) 就是我们的答案啦！
完结放上代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void Write(int x){
if(x>9) Write(x/10);
putchar(x%10+48);
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
Write(x);
putchar('\n');
}
}
using namespace Testify;
const int N=1e5+555;
int n,a[N],maxn=-1,id[N],op;
int sum[N][2],b[N];
int dp[70][N];
inline bool cmp(int x,int y){
return b[x]<b[y];
}
main(){
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
n=read();
for(register int i=1;i<=n;i++){
a[i]=read();
}
stable_sort(a+1,a+n+1);
for(register int i=1;i<=n;i++){
a[i]=a[n]-a[i];
}
for(register int k=0;k<=60;k++){
op=(1ll<<k)-1;
for(register int i=1;i<=n;i++){
b[i]=(a[i]&op);
id[i]=i;
}
stable_sort(id+1,id+n+1,cmp);
for(register int i=1;i<=n;i++){
sum[i][0]=sum[i-1][0];
sum[i][1]=sum[i-1][1];
sum[i][(a[id[i]]>>k)&1]++;
}
int allcount=sum[n][1];
for(register int i=0;i<=n;i++){//进位
int nowcount=sum[n][1]-sum[n-i][1];
int zuo=nowcount;
int you=i-nowcount+allcount-nowcount;
dp[k+1][zuo]=min(dp[k+1][zuo],dp[k][i]+you);
zuo=allcount-nowcount+i;
you=nowcount+(n-i)-(allcount-nowcount);
dp[k+1][zuo]=min(dp[k+1][zuo],dp[k][i]+you);
}
}
write(dp[61][0]);
return 0;
}