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?
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 one integer the minimum number of operations required to make all the chemicals volumes equal.
3
4 8 2
2
3
3 5 6
5
In the first sample test, the optimal solution is to divide the second chemical volume by two, and multiply the third chemical volume by two to make all the volumes equal 4.
In the second sample test, the optimal solution is to divide the first chemical volume by two, and divide the second and the third chemical volumes by two twice to make all the volumes equal 1.
题目分析 ：
给你 n 个数，有两种操作可以执行，一是将此数扩大 2 倍， 二是将此数变为 一半。
思路分析 ：
最初想的是 广搜， n 个数, 数据范围是 1e5 ，每次乘以 2 ，总的操作数加起来也没有多少，所以对每个数都进行广搜，但是如果只是单纯这么写一直都是超时，后来一位 丁学长指导了下， 每次记步数的数组清空只清空之前用过的地方，这个地方一优化题目就直接过了。
const int eps = 1e5+5;
const double pi = acos(-1.0);
const int inf = 1<<29;
#define Max(a,b) a>`b?a:b
#define Min(a,b) a>b?b:a
#define ll long long
int pre[eps];
int bu[eps];
int pt[eps];
int p[eps];
queue<int>que;
stack<int>s;
int maxn = 0x3f3f3f3f;
void bfs(int num){
while(!que.empty()) que.pop();
que.push(num);
p[num] = 0;
s.push(num);
while(!que.empty()) {
int x = que.front();
que.pop();
int x1 = x / 2;
int x2 = x*2;
if (x1 >= 1 && x1 <= maxn && p[x1] == -1) {
p[x1] = p[x] + 1;
que.push(x1);
bu[x1] += p[x1];
pt[x1]++;
s.push(x1);
}
if (x2 <= eps && x2 <= maxn && p[x2] == -1){
que.push(x2);
p[x2] = p[x] + 1;
bu[x2] += p[x2];
pt[x2]++;
s.push(x2);
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%d", &pre[i]);
maxn = max(maxn, pre[i]);
}
memset(p, -1, sizeof(p));
for(int i = 1; i <= n; i++){
pt[pre[i]]++;
bfs(pre[i]);
while(!s.empty()) {
int x = s.top();
s.pop();
p[x] = -1;
}
}
int ans = 0x3f3f3f3f;
for(int i = 1; i <= 100000; i++){
if (pt[i] == n) {
ans = min(ans, bu[i]);
}
}
printf("%d
", ans);
return 0;
}
题目还有种方法就是直接暴力，队于每个数如果它是奇数，你除以 2 在乘以 2 ，会得到一组新的不同的数，但是如果是偶数的此过程就没有意义。
const int eps = 1e5+5;
const double pi = acos(-1.0);
const int inf = 1<<29;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define ll long long
int pre[eps];
int bu[eps];
int cnt[eps];
void fun(int x) {
int p = x;
int k = 0;
while(p <= 100000){
cnt[p]++;
bu[p] += k++;
p *= 2;
}
p = x;
k = 0;
while(p > 1) {
int f = p/2;
k++;
cnt[f]++;
bu[f] += k;
if (p & 1) {
int ff = f*2;
int kk = k+1;
while(ff <= 100000){
cnt[ff]++;
bu[ff] += kk++;
ff *= 2;
}
}
p /= 2;
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%d", &pre[i]);
}
for(int i = 1; i <= n; i++){
fun(pre[i]);
}
int ans = 0x3f3f3f3f;
for(int i = 1; i <= 100000; i++){
if (cnt[i] == n) {
ans = min(ans, bu[i]);
}
}
printf("%d
", ans);
return 0;
}