设为首页 加入收藏

TOP

Codeforces Amr and Chemistry（数学+乱搞）
2015-07-24 05:00:08 来源: 作者: 【大 中 小】 浏览:5次
Tags：Codeforces Amr and Chemistry 数学 乱搞

题意：给n个数，每个数每次可以乘二或除以二（向下取整相当于左移或右移），问最少经过多少次操作可以使这n个数变相等。

思路：首先考虑每个数的可能取值，将一个数表示成s*2^k的形式，s是奇数。

那么这个数的所有可能取值为s'*2^x,(s'=s/2,(s/2)/2,.....)且s'*2^x<=100000

因为这题数据范围不大，而且每个值可能的取值不多最多几百个，所以记录1到100000每个值可能被取到的次数以及总操作数，最后从1遍历到100000取最小的ans即可

ps：个人赛这道题做了一下午无数乱搞写的代码巨恶心......晚上回来优化了一下勉强能看..........

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long using namespace std; //const int maxn = 100 + 5; const int INF = 100000000; int n, abc; int vol[100010], ans[100010]; //vol代表每个容量可能被取到的次数，ans表示取到该容量所要的操作总数 int main() { // freopen(input.txt, r, stdin); while(scanf(%d, &n) == 1) { memset(vol, 0, sizeof(vol)); memset(ans, 0, sizeof(ans)); for(int i = 0; i < n; i++) { cin >> abc; int t = abc; int cnt = 1, cnt1 = 0; abc <<= 1; while(abc <= 100000) { vol[abc]++; ans[abc] += cnt; cnt++; abc <<= 1; } cnt = 0; while(t%2 == 0) { vol[t]++; ans[t] += cnt; cnt++; cnt1++; t >>= 1; } vol[t]++; ans[t] += cnt; t >>= 1; cnt1++; while(t != 0) { int u = t; int cnt2 = cnt1; while(u <= 100000) { vol[u]++; ans[u] += cnt2; cnt2++; u <<= 1; } if(t%2 == 0) { while(t%2 == 0) { t >>= 1; cnt1++; vol[t]++; ans[t] += cnt1; } } t >>= 1; cnt1++; } } int pans = INF; for(int i = 0; i <= 100000; i++) if(vol[i] == n) pans = min(pans, ans[i]); //cout << vol[2] << endl << vol[1] << endl << vol[8] << endl; cout << pans << endl; } return 0; }

?

?

?

??

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdoj-1197-Specialized Four-Digi.. 下一篇：HDU 5089 Assignment（rmq+二分 ..

评论

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