CodeForces 558C Amr and Chemistry （位运算，数论，规律，枚举）-白红宇

CodeForces 558C Amr and Chemistry （位运算，数论，规律，枚举）

阅读量：6702 次

发布时间：2019-06-25

本文共 1533 字，大约阅读时间需要 5 分钟。

题意：给n个数字，对每一个数字能够进行两种操作：num*2与num/2（向下取整），求：让n个数相等最少须要操作多少次。

分析：

计算每一个数的二进制公共前缀.

枚举法亦可。

/**Author : Flint_x *Created Time : 2015-07-22 12:33:11 *File name : whust2_L.cpp */#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #define inf 2139062143using namespace std;const double eps(1e-8);typedef long long lint;#define cls(a) memset(a,0,sizeof(a))#define rise(i,a,b) for(int i = a ; i <= b ; i++)#define fall(i,a,b) for(int i = a ; i >= b ; i--)const int maxn = 100000 + 5;int num[maxn];int temp[maxn];int odd[maxn],cnt[maxn];int n;int main(){ // freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout); while(cin >> n){ for(int i = 1 ; i <= n ; i++){ scanf("%d",&num[i]); } cls(cnt);cls(odd); sort(num+1,num+n+1); for(int i = 1 ; i <= n ; i++) temp[i] = num[i]; int t = num[1]; for(int i = 1 ; i <= n ; i++){ while(t ^ num[i]){ if (t < num[i]) num[i] >>= 1; else t >>= 1; } } for(int i = 1 ; i <= n ; i++) num[i] = temp[i]; for(int i = 1 ; i <= n ; i++){ while (num[i] ^ t){ cnt[i]--; if(num[i] % 2) odd[i] = cnt[i]; num[i] >>= 1; } } lint ans = inf; for(int i = 0 ; i < 20 ; i++){ lint x = 0; for(int j = 1 ; j <= n ; j++){ if (odd[j] == 0 || cnt[j] + i <= odd[j]) x += abs(cnt[j] + i); else x += abs(odd[j]) + abs(odd[j] - (cnt[j] + i)); }// cout << x << endl; ans = min(ans,x); } cout << ans << endl; } return 0;}