C. Amr and Chemistry
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/558/problem/C
Description
Amr loves Chemistry, and specially doing experiments. He is preparing for a new interesting experiment.
Amr has n different types of chemicals. Each chemical i has an initial volume of ai liters. For this experiment, Amr has to mix all the chemicals together, but all the chemicals volumes must be equal first. So his task is to make all the chemicals volumes equal.
To do this, Amr can do two different kind of operations.
Choose some chemical i and double its current volume so the new volume will be 2ai
Choose some chemical i and divide its volume by two (integer division) so the new volume will be
Suppose that each chemical is contained in a vessel of infinite volume. Now Amr wonders what is the minimum number of operations required to make all the chemicals volumes equal?
Input
The first line contains one number n (1 ≤ n ≤ 105), the number of chemicals.
The second line contains n space separated integers ai (1 ≤ ai ≤ 105), representing the initial volume of the i-th chemical in liters.
Output
Output one integer the minimum number of operations required to make all the chemicals volumes equal.
Sample Input
3
4 8 2
Sample Output
2
HINT
题意
给你一个序列，你有俩操作，可以使得一个数乘以2，也可以使得一个数除以2
然后问你最少进行多少个操作，可以使得所有数都一样
题解：
直接暴力跑就好了，但是这里有一个人问题，比如5/2=2 2×2=4，这样就不一样了怎么办？
一样暴力就好了，当出现奇数的时候，直接暴力乘以2网上爬
代码
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 2000001 #define mod 10007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** int cnt[maxn],num[maxn]; int a[maxn]; int main() { int n=read(); for(int i=0;i<n;i++) { int x=read(); int pre=0; while(x) { int s=0; while(x%2==0) { x/=2; s++; } int y=x; int j=0; while(y<maxn) { cnt[y]++; num[y]+=pre+abs(j-s); j++; y*=2; } pre+=s+1; x/=2; } } int ans=inf; for(int i=1;i<maxn;i++) { if(cnt[i]==n) ans=min(ans,num[i]); } cout<<ans<<endl; }