首页 > 其他 > 详细

思维+暴力

时间:2019-08-21 16:41:25      阅读:66      评论:0      收藏:0      [点我收藏+]

1483 化学变换

 

有n种不同的化学试剂。第i种有ai升。每次实验都要把所有的化学试剂混在一起,但是这些试剂的量一定要相等。所以现在的首要任务是把这些化学试剂的量弄成相等。

有两种操作:

把第i种的量翻倍,即第i种的量变成2ai。

把第i种的量减半,除的时候向下取整,即把第i种的量变成  ????2 ⌊ ai2 ⌋ 。

现在所有的化学试剂的量已知,问最少要变换多少次,这些化学试剂的量才会相等。

样例解释:把8变成4,把2变成4。这样就需要两次就可以了。

 

输入

单组测试数据。
第一行有一个整数n (1 ≤ n ≤ 10^5),表示化学物品的数量。
第二行有n个以空格分开的整数ai (1 ≤ ai ≤ 10^5),表示第i种化学试剂的量。

输出

输出一个数字,表示最少的变化次数。

输入样例

3
4 8 2

输出样例

2


思路:我们可以将每个数进行乘和除所得到的数都写出来,然后看哪一个数出现过n次并且次数最少,输出。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxx=2e5+10;
ll a[maxx];
ll vis[maxx];//geshu
ll cishu[maxx];//cishu


void f(ll b)
{
    ll tmp=b;
    ll ci=0;
    while(tmp<=1e5)
    {
        vis[tmp]++;
        cishu[tmp]+=ci;
        ci++;
        tmp*=2;
    }
    ll t=b;
    ci=0;
    while(t)
    {
        if(t%2==1&&t!=1)
        {
            t/=2;
            ci++;
            vis[t]++;
            cishu[t]+=ci;
            ll tt=t;
            ll cc=ci;
            while(tt<=1e5)
            {
                cc++;
                tt*=2;
                vis[tt]++;
                cishu[tt]+=cc;
                
            }
        }
        else
        {
            t/=2;
            ci++;
            vis[t]++;
            cishu[t]+=ci;
        }
    }

}
int main()
{
    ll n,i;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;i++)
        f(a[i]);
    ll ans=0x3f3f3f3f;
    for(i=0;i<=2e5+10;i++)
    {
        if(vis[i]==n)
        {
            ans=min(cishu[i],ans);
        }
    }
    printf("%lld\n",ans);

}

 

思维+暴力

原文:https://www.cnblogs.com/bhd123/p/11389053.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!