题解 CF1188D 【Make Equal】

· · 题解

题意：给定一个序列，每次可以选一个数并将其加上2的幂次方，求使所有数相等的最少步数。

原题

真心感谢 x义x 神仙。

可能是我理解能力堪忧，感觉其它题解讲的有些简略。

有一个朴素而naive的想法就是算出每个数与最大值的差值，算一下二进制下有几个1就好了。令 x 二进制下有几个一 为 bitof(x)

可惜看一眼样例就知道假掉了。因为可以对最大值进行操作，从而使答案变优。

那么，如果令最大值增加 delta ，答案即是\sum bitof((delta+maxx-a(i)))(maxx为原数列中最大值)

为了方便，令a_i=maxx-a_i。我们要决策 delta。

那么我们一位一位的来尝试DP。

对于每一位，要考虑 delta 和 a_i 这一位取值的影响，以及麻烦的上一位进位的影响。

其中 delta 是我们要决策的东西，a_i 已知，上一位进位的影响只能再开一维记录了。

乍一看，好哇，2^n 个状态，太好了。

但是仔细一想，似乎越大的越容易进位。这里的“越大的”指的是当前考虑的位数以下的大小。

那只要记录上一位有几个进位的就好了，因为我们知道进位的一定是按当前考虑的位数以下的大小降序排列后的前几位。

那么状态就只有 n 个了，由于一共有 \log(w) 位，空间复杂度n \log(w)（w 是值域）

令 dp[i][j] 表示 前 i 位，第 i 位有 j 个进位时的最优解。

接着，考虑排序后如何转移：（具体）

可以发现我们不关心这个数到底是多少，只关心1的数量和进位的数量

如果钦定上次前 j 位进位，那么数一共就有4种。

令 cnt 为这一位数中1的总数， tot 为前 j 个数这一位1的总数。

1：上次进位，这一位是1，有 tot 个。\ 2：上次进位，这一位是0，j-tot 个。\ 3：上次未进位，这一位是1，cnt-tot 个。\ 4：上次未进位，这一位是0，n-j-(cnt-tot) 个。

那么，开始决策：

$delta$ 这一位取0：$1$进位，$2,3$ 这一位是1。 那么就很简单了。 我们不断希望按二进制某一位前的大小排序，而基数排序与此相当契合，所以排序可以用基数排序实现，从而让复杂度从直接快排的 $n \log{n} \log{w}$ 降到 $n \log{w}$。 如果用快排的话，记得不要用取模写比较函数，否则你会喜提最劣解。用二进制快4倍…… $\texttt{Talk is cheap,show me your code.} 
#include <cstdio>
#include <algorithm>
#include <vector>

typedef long long ll;
const int maxn=1e5+5,lim=62,maxm=65;const ll inf=1e18;

template<typename T> inline T min(T a,T b){
    return a<b?a:b;
}

int n;ll a[maxn],mod,dp[maxm][maxn];

// inline bool Comp(ll a,ll b){
//  return (a%mod)>(b%mod);
// }

inline bool Comp(ll a,ll b){
    return a>b;
}

void radix_sort(){
    std::vector<ll> bit[2];
    for(int i=1;i<=n;i++){
        bit[(a[i]&(1ll<<(mod-1)))>0ll].push_back(a[i]);
    }
    int cnt=0;
    for(int i=0;i<bit[1].size();i++) a[++cnt]=bit[1][i];
    for(int i=0;i<bit[0].size();i++) a[++cnt]=bit[0][i];
}

int main(){
    scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    std::sort(a+1,a+n+1,Comp);
    for(int i=n;i>=1;i--) a[i]=a[1]-a[i];
    for(int i=0;i<=lim;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=0;i<lim;i++){
        mod=i;if(i) radix_sort();//如果是在第0位，不需要排序
        ll cnt=0,tot=0;mod=1ll<<i;
        for(int j=1;j<=n;j++){
            cnt+=a[j]&mod?1:0;
        }
        for(int j=0;j<=n;j++){
            tot+=a[j]&mod?1:0;
            //x[i]->1,1~j:1->1,+1,0->0,+1 j+1~n:1->0,+1,0->1,+0
            dp[i+1][cnt-tot+j]=min(dp[i+1][cnt-tot+j],dp[i][j]+tot+(n-j)-(cnt-tot));
            //x[i]->0,1~j:1->0,+1,0->1,+0 j+1~n:1->1,+0,0->0,+0
            dp[i+1][tot]=min(dp[i+1][tot],dp[i][j]+j-tot+cnt-tot);
        }
    }
    printf("%lld\n",dp[lim][0]);
    return 0;
}