Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/contest/558/problem/C
题目大意是说，给定N个数，可以对任意数进行任意次两种操作，×2，和/2（整除）
问最少操作多少次，可以让所有数相等。
嘛，前半个小时A掉了前两个提，d E貌似都是线段树。。并不会。。。就一直搞C。。。。
然而并没有做出来。位运算是什么神奇的黑魔法。
转载一份题解：http://blog.csdn.net/qq_24451605/article/details/46906813
思路是声明两个数组，一个数组表示到达i的步数，另一个数组表示n个数中能够达到i的数的个数（包括本身）
1
2 /*************************************************************************
3 > File Name: code/#312C.cpp
4 > Author: 111qqz
5 > Email: rkz2013@126.com
6 > Created Time: Mon 20 Jul 2015 11:36:50 PM CST
7 ************************************************************************/
8
9 #include<iostream>
10 #include<iomanip>
11 #include<cstdio>
12 #include<algorithm>
13 #include<cmath>
14 #include<cstring>
15 #include<string>
16 #include<map>
17 #include<set>
18 #include<queue>
19 #include<vector>
20 #include<stack>
21 using namespace std;
22 #define REP(i, n) for (int i=0;i<int(n);++i)
23 typedef long long LL;
24 typedef unsigned long long ULL;
25 const int N= 1E5+7;
26 const int inf = 0x7fffffff;
27 int a[N];
28 int vis[N],step[N];
29 bool cmp (int a,int b)
30 {
31 if (a>b) return true;
32 return false;
33 }
34 int main()
35 {
36 int n;
37 cin>>n;
38 int mx = -1;
39 memset(vis,0,sizeof(vis));
40 memset(step,0,sizeof(step));
41
42 for ( int i = 1 ; i <= n ; i++ )
43 {
44 cin>>a[i];
45 if (a[i]>mx)
46 mx = a[i];
47 }
48 for ( int i = 1 ; i <= n ; i++ )f
49 {
50 int tmp = a[i];
51 int num = 0;
52 while (tmp<=mx)
53 {
54 step[tmp]+=num; //到达tmp需要的操作数是之前的数到达tmo的操作数加上当前
55 vis[tmp]++; //能够到达i的数的个数存在vis数组
56 num++;
57 tmp = tmp << 1;
58 }
59 num = 0;
60 int tmpa = a[i];
61 while (tmpa)
62 {
63 if (tmpa&1&&tmpa!=1) //a[i]&1为真当且仅当a[i]的二进制表示的最后一位是1，即a[i]为奇数
64 { //但是如果a[i]为1，/2为0，就无法变大了。
65 int tmp = (tmpa>>1)<<1;
66 int sum = num + 2; //奇数a[i]变为偶数a[i]-1的需要两步。
67 while (tmp<=mx) //再从a[i]-1扩展下去，看能达到哪些数。
68 {
69 step[tmp]=step[tmp]+sum;
70 vis[tmp]++;
71 sum++;
72 tmp = tmp << 1;
73 }
74 }
75 num++; //往反方向扩展，看能达到哪些数。
76 tmpa = tmpa>>1; //注意a[i]在之前已经达到过了。
77 step[tmpa]+=num;
78 vis[tmpa]++;
79 }
80
81 }
82 int ans = inf;
83 for ( int i = 1 ; i <= mx ; i++ )
84 {
85 // cout<<"i:"<<i<<" vis[i]:"<<vis[i]<<" step[i]:"<<step[i]<<endl;
86 if (vis[i]==n)
87 {
88 ans = min(ans,step[i]);
89 }
90 }
91 cout<<ans<<endl;
92
93
94
95 return 0;
96 }