http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1483
首先，要知道在0---4e5内的体积下，一定存在答案。不会存在一些更大的答案。（要证明我也不晓得，我直觉）
那么我的思路就是，枚举，0--4e5，然后需要O（1）判断和更新答案。
那么预处理isok[cnt]表示产生cnt这个数字，其中有两个参数，has，表示一共有多少个数能产生这个数字。那么明显has需要等于n，才是答案的贡献。然后step，表示这n个数产生cnt这个数字，需要的步数的总和。这个可以用dfs维护。每次要么 * 2，要么 / 2，产生相同的数字，就可以return了、最优的复杂度是偶数的情况，是logn。奇数的话，也就多了几个常数，因为 / 2多次（应该不超过3次），都会变成偶数
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e5 + 20; int mx; struct node { int step; int has; }isok[maxn * 4]; int vis[maxn * 4]; int DFN; void calc(int x, int cnt) { if (x >= mx) return; if (vis[x] == DFN) return ; vis[x] = DFN; isok[x].step += cnt; isok[x].has++; calc(x * 2, cnt + 1); calc(x / 2, cnt + 1); } void work() { int n; scanf("%d", &n); mx = 4e5; for (int i = 1; i <= n; ++i) { int x; DFN++; scanf("%d", &x); calc(x, 0); } int ans = inf; for (int i = 0; i <= mx; ++i) { if (isok[i].has != n) continue; ans = min(ans, isok[i].step); } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
原文：http://www.cnblogs.com/liuweimingcprogram/p/6390284.html
