专栏文章

CF2118C Make It Beautiful 题解

MMier_Samuelle
CF2118C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip3jp2d
此快照首次捕获于
2025/12/03 05:35
3 个月前
此快照最后确认于
2025/12/03 05:35
3 个月前
查看原文
不难想到，若要使一个数的贡献增加 11，必定将其最低的数位 00 改为 11。
于是我们预处理 ci,jc_{i,j}，表示使 aia_i 的贡献变为 jj 所需要的最小代价（即操作次数）。这部分可以做到 O(nlog⁡V)O(n \log V)，其中 V=1018V=10^{18}。
不难想到，每次操作必定选择一个代价最小的 aia_i，使其贡献增加 11。这部分可以用优先队列做到 O(nlog⁡nlog⁡V)O(n \log n \log V)。
具体实现见代码。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...