有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