设为首页 加入收藏

TOP

Codeforces 558C Amr and Chemistry 规律
2015-11-21 00:57:13 来源: 作者: 【大 中 小】 浏览:3次
Tags：Codeforces 558C Amr and Chemistry 规律

题目链接

题意：

给定n长的序列

每次可以选一个数 让其 *=2 或者 /=2

问至少操作多少次使得所有数相等。

思路：

对于每个数，计算出这个数可以变成哪些数，以及变成那个数的最小步数。

cnt[i] 表示序列中有cnt个数可以变成i

step[i] 表示能变成i的 那些数 变成i的花费和是多少。

notice: if a[i] == 7, a[i] also can reach 6. by /=2 then *=2

7->3->1..

3->6->12

1->2->4

只要是奇数（不包括1） 就能花费2步到达 a[i]-1的位置

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include
        #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; template 
               
                 inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template 
                
                  inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } typedef long long ll; typedef pair
                 
                   pii; const int N = 200005; const int inf = 1e9 + 10; int n; int a[N]; int cnt[N], step[N]; void up(int y, int s) { //向上枚举 while (y < N) { cnt[y]++; step[y] += s; y <<= 1; s++; } } void go(int y) { up(y, 0); int now = 1; while (y) { //使y一直向下减小 if ((y > 1) && (y & 1)) { y >>= 1; up(y, now); } else { y >>= 1; cnt[y]++; step[y] += now; } now++; } } int main() { while (cin >> n) { memset(cnt, 0, sizeof cnt); memset(step, 0, sizeof step); for (int i = 1; i <= n; i++) { rd(a[i]); go(a[i]); } int ans = step[1]; for (int i = 2; i < N; i++) { if (cnt[i] == n) ans = min(ans, step[i]); } pt(ans); } return 0; }


?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：[LeetCode][Java] Spiral Matrix .. 下一篇：Tri Tiling（hdu1143）

评论

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