codeforces 558c Amr and Chemistry (贪心)

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: [email protected]
 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    }
97