CF1213D1的题解

（一）

直接暴力！！！

对于每一个数，枚举它能生成的数。

然后对于每一个可能的答案，开长度为 \(k\) 的优先队列维护，同时统计操作次数和。

时间复杂度为 \(Θ(\log^2_2n)\)。
惊讶地发现顺便把双倍经验给切了。（卡过）

（二）

AC 代码。

#include<bits/stdc++.h>
using namespace std;
int cnt,n,k,sum[200010],ans=INT_MAX;
priority_queue<int>q[200010];
void add(int x,int pos){
	if(q[pos].size()<k)sum[pos]+=x,q[pos].push(x);
	else if(q[pos].top()>x){
		sum[pos]-=q[pos].top();
		q[pos].pop();
		sum[pos]+=x;
		q[pos].push(x);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		add(0,x);
		int cnt=0;
		while(x){
			cnt++;
			x>>=1;
			add(cnt,x);
		}
	}
	for(int i=0;i<=200000;i++)
		if(q[i].size()==k)ans=min(ans,sum[i]);
	printf("%d",ans);
	return 0;
}