设为首页 加入收藏

TOP

CodeForces 558C Amr and Chemistry （位运算，数论，规律，枚举）
2015-07-24 05:00:20 来源: 作者: 【大 中 小】 浏览:6次
Tags：CodeForces 558C Amr and Chemistry 运算 数论 规律 枚举

Codeforces 558C

题意：给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 2139062143 using 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; }


?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：1336 - Fixing the Great Wall（D.. 下一篇：UVA 10917 Walk Through the Fore..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: