cf题面 中文题意 给n个数，每次可以把其中一个数字位运算右移一位（即整除以二），问要至少操作几次才能让这n个数中有至少k个相等。 解题思路 这题还有个数据范围更小的简单版本
cf题面
中文题意
给n个数，每次可以把其中一个数字位运算右移一位（即整除以二），问要至少操作几次才能让这n个数中有至少k个相等。
解题思路
这题还有个数据范围更小的简单版本，n和k是50，\(a_i\)还是2e5。
发现\(1\leqslant a_i\leqslant 2?10^5\)，这些数字除以二只会变小，换句话说，整个过程中数字大小都不会超过\(2?10^5\)，然后就可以用类似桶排序的方法，把所有数字不停除以二，把得到一个数字所用的步骤数（包括0步，即原数字）扔到相应的桶里，之后统计每个桶，有没有k个数，如果有，就计算其中最小的k个步骤数之和，用于更新答案。（感觉这段话还不如代码好懂）
这种思维题，标签都不好打，就模仿cf，给这题打个“暴力”的标签算了
源代码
#include<vector>
#include<cstdio>
#include<algorithm>
const int MAXN=2e5+5;
int n,k,mxa;
std::vector<int> t[MAXN];//t[i]表示达到i的操作次数
int main()
{
scanf("%d%d",&n,&k);
while(n--)
{
int a;
scanf("%d",&a);
mxa=std::max(mxa,a);
int cur=0;
while(a)
{
t[a].push_back(cur);
cur++;
a>>=1;
}
t[0].push_back(cur);
}
int ans=0x7fffffff;
for(int i=0;i<=mxa;i++)
{
if(t[i].size()<k) continue;
std::sort(t[i].begin(),t[i].end());
int sum=0;
for(int j=0;j<k;j++) sum+=t[i][j];//题解标程使用了accumulate函数
ans=std::min(ans,sum);
}
printf("%d\n",ans);
return 0;
}