补题 | CF2246D

题目

You are given an array ​a of ​n integers. Alice and Bob will play a game with this array.

Before the game with Bob starts, Alice can increment any element of the array any number of times, each increment taking one move. One increment consists of a single addition by ​1 to one index.

After that, the game starts and Bob and Alice take turns, with Bob making the first move. On Bob's turn, he can choose any two indices ​i and ​j and swap the array elements at these indices (note that Bob may choose ​i = j, in which case the array remains unchanged after the swap).

On Alice's turn, if ​a_1 is even, she finds the largest ​j \leq |a| such that ​a_i is even for all ​i \leq j, then sets ​a_i := a_i/2 for ​i \leq j. Otherwise she sets ​a_1 := a_1 - 1. If any element becomes zero, it automatically gets erased from the array (and the other elements are re-indexed accordingly).

The game ends when the array is empty.

Alice wants to minimize the number of moves she makes, while Bob wants to maximize the number of moves Alice makes. Note that the number of moves is the sum of the number of initial additions and the number of turns Alice plays after.

How many moves will Alice make with optimal play?

做法

容易发现，只要数列当中存在奇数，那么 Bob 一定可以利用奇数使得 Alice 最多操作一个偶数，于是容易得到 Alice 操作流程。初始化 -> 同除 ​2^k (k \in N) -> 一个个变为0 。

最终的步骤数是容易得到的，关键在于如何初始化，首先样例已经提示不一定存在同除步骤 （即其中 ​k=0 ）。形式化的，记处理后的数组为 ​b_i ，题目目标即最小化：

其中 ​step(x) 是 ​x 归零需要的步数，​count_2(x) 是 ​x 分解素因数后 ​2 的次幂。

注意到数列中的数均小于 ​10^5 ，那么枚举同除次数一定不会太多，可以尝试枚举同除次数 ​t ，对每个数，计算 ​\min_{b \ge a_i, 2^t \mid b}(b-a_i+step(b)) 即可。

下面证明，为什么提升到最近的 ​2^r 的倍数一定是最好的，首先对 ​b 分解素因数，记其中 ​2 的次幂为 ​r ，即将 ​b 改写成 ​q \cdot 2^r ，其中 ​q 为奇数，取 ​b'=(q-1)2^r 这里不妨假设 ​b' \ge a ，同除以 ​2^t , 有 ​step(\frac b {2^t})=step(\frac {b'} {2^t}) + 1 ，展开总成本，有：

因此只要存在这样的 ​b' , ​b 就一定不是最优的，即满足 ​b-2^r<a \le b . 得证取 ​b=\left\lceil\frac a{2^r}\right\rceil 2^r .

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
int get(ll x){
    int cnt=0;
    while((x&1)==0&&x>0){
        x>>=1;
        cnt++;
    }
    return cnt;
}
int getstep(ll x){
    int len=0,cnt=0;
    while(x){
        len++;
        cnt+=x&1;
        x>>=1;
    }
    return len-1+cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<ll> a(n+1);
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        ll ans=INF;
        for(int minget=0;minget<=18;minget++){
            ll cnt=minget; // 假如同除
            for(int i=1;i<=n;i++){
                ll best=INF;
                for(int nowget=minget;nowget<=18;nowget++){
                    ll tmp=1<<nowget;
                    ll x=(a[i]+tmp-1)/tmp*tmp;
                    ll cost=x-a[i]+getstep(x/tmp*(1<<(nowget-minget)));
                    best=min(best,cost);
                }
                cnt+=best;
            }
            ans=min(ans,cnt);
        }
        cout<<ans<<"\n";
    }
    return 0;
}