题目链接 : CodeForces 558C
题目大意
给你n个数，每个数 ai 可以做两种变换， ai = ai*2 ; ai = ai/2;
问最少经过多少次变换能使所有的数相同
例如 4 8 2 （8 -> 4 2 -> 4） 最少需要变换2次；
给个样例
5 4 4 （5 -> 2， 2->4） 也是最小需要两次；
思路
每个数乘2 或者除2 ， 有没有想到什么？ 没错就是位运算。 我们可以通过位运算枚举出每一个数 ai 可以转变成的数， 以及变成这个数所需要的转换次数。
用visit[ i ]储存可以转变到的数 i 的次数， 用 cnt[ i ]储存转变到 数 i 所需要的步数。
因此最后我们只要枚举所有visit[ i ] 等于 n 的数，并求出对应最小的 cnt[ i ]，就行了。
①向上枚举到 1e5
②向下枚举
如果 ai 是奇数 ， 则先保存 ai>>1 的数据， 然后再将 ai <<1 左移直到1e5 （想想为什么 ， 参照上面的样例）
如果是偶数，直接保存 ai>>1 的数据。
③枚举 1 ~ 2e5 所有的visit[ i ]，比较对应的cnt[ i ]，找到最小值。
源代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100000 + 10;
int vis[maxn*2];
int cnt[maxn*2];
void deal(int n){int tmp = n;int tmp2 = n;int instep = 0;int instep2 = 0;while(tmp <= (int)1e5){ //向上枚举vis[tmp]++;cnt[tmp]+= instep;instep ++;tmp <<= 1;}while(tmp2){ //向下枚举if((tmp2 & 1) && tmp2 != 1){ //如果是奇数， 切奇数不为1tmp2 >>=1; //先/2instep2++;cnt[tmp2]+=instep2;vis[tmp2]++;int tt = tmp2;int instep = instep2;while(tt <= (int)1e5){ //向上枚举tt <<= 1;instep ++;vis[tt]++;cnt[tt]+=instep;}}else{ //偶数 或者 1instep2++;tmp2 >>= 1;vis[tmp2]++;cnt[tmp2] += instep2; }}
}
int main(){int n;while(scanf("%d",&n)!=EOF){memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(cnt));int tmp;for(int i=0;i<n;i++){scanf("%d",&tmp);deal(tmp); //对于每一个数 ， 用位运算枚举出它所有能变成的数}int res = 99999999;for(int i=0;i<(int)(2*1e5);i++){if(vis[i] == n){// cout<<i<<" "<<cnt[i]<<" dd"<<endl;res = min(res,cnt[i]);}}printf("%d\n",res);}return 0;
}
