CF2118C Make It Beautiful 题解

Mier_Samuelle · 2025-06-13 16:54:08 · 题解

不难想到，若要使一个数的贡献增加 1，必定将其最低的数位 0 改为 1。

于是我们预处理 c_{i,j}，表示使 a_i 的贡献变为 j 所需要的最小代价（即操作次数）。这部分可以做到 O(n \log V)，其中 V=10^{18}。

不难想到，每次操作必定选择一个代价最小的 a_i，使其贡献增加 1。这部分可以用优先队列做到 O(n \log n \log V)。

具体实现见代码。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5010, MAXM = 70;
int a[MAXN], cost[MAXN][MAXM];
struct Node{
    int cost, i, j;
};
bool operator > (Node x, Node y){
    return x.cost > y.cost;
}
void solve(){
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> a[i], ans += __builtin_popcount(a[i]);
    for (int i = 1;i <= n;i++){
        int ind = 0;
        for (int j = 1;j <= 63;j++){
            while (a[i] & (1ll << ind)) ind++;
            int na = a[i] | (1ll << ind);
            cost[i][j] = na - a[i];
            ind++;
        }
    }
    priority_queue <Node, vector<Node>, greater<Node>> q;
    for (int i = 1;i <= n;i++) q.push({cost[i][1], i, 1});
    while (k > 0 && !q.empty()){
        int c = q.top().cost, i = q.top().i, j = q.top().j;
        q.pop();
        if (k >= c){
            k -= c;
            ans++;
            q.push({cost[i][j + 1], i, j + 1});
        }
    }
    cout << ans << endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}