51nod 1483 化学变换 | 二进制 暴力

51nod 1483 化学变换

题面

给出n个整数(n <= 1e5，每个数 <= 1e5)，对每个数都可以进行多次操作，操作有两种：乘二/整除以二。

问最少经过多少次操作能使所有数相等。

题解

对于每个数，枚举它变成另外一个数（目标数）所需的最小步数，目标数的代价值 += 这个最小步数。这样最后输出所有目标数中代价值最小的即可。

注意，对于一个奇数，把它除以二之后再乘以二，得到的是一个新数。

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <iostream>

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

bool read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

	else if(c == EOF) return 0;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

    return 1;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 100005;

int n, a[N], sum[N], vis[N], cnt[N], ans = 0x7fffffff;

void add(int i, int t, int step){

    vis[t] = i;

    cnt[t]++;

    sum[t] += step;

}

int main(){

    read(n);

    for(int i = 1; i <= n; i++)

	read(a[i]);

    for(int i = 1; i <= n; i++){

	int t = a[i], step = 0;

	while(t < N){

	    add(i, t, step);

	    t <<= 1, step++;

	}

	t = a[i], step = 0;

	while(t){

	    t >>= 1, step++;

	    int tt = t, tstep = step;

	    while(tt < N && vis[tt] != i){

		add(i, tt, tstep);

		tt <<= 1, tstep++;

	    }

	}

    }

    for(int i = 1; i < N; i++)

	if(cnt[i] == n)

	    ans = min(ans, sum[i]);

    write(ans), enter;

    return 0;

}