51Nod－1483－化学变换

ACM模版

描述

题解

枚举暴力解题即可。枚举每一个数可能产生的数，并且记录产生该数的步数，最后取最少的总步数。

代码

#include <iostream> #include <cstring> using namespace std; const int MAXN = 1e5 + 10; const int INF = 0x3f3f3f3f; int num[MAXN]; int sum[MAXN]; int N; // 翻倍 void F(int temp, int cnt) { for (temp = temp * 2, cnt++; temp < MAXN; temp *= 2, cnt++) { num[temp]++; sum[temp] += cnt; } return ; } int main(int argc, const char * argv[]) { while (cin >> N) { memset(num, 0, sizeof(num)); memset(sum, 0, sizeof(num)); for (int i = 0; i < N; i++) { int a, cnt = 0; cin >> a; bool flag = true; while (a) { num[a]++; sum[a] += cnt; if (flag) { F(a, cnt); } if (a & 1) // 如果是奇数，折半向下取整后可以继续翻倍 { flag = true; } else // 如果是偶数，则不能继续翻倍 { flag = false; } a /= 2; // 折半(向下取整) cnt++; } } int ans = INF; for (int i = 0; i < MAXN; i++) { if (num[i] == N) // 可以全部变换到这个状态 { ans = min(ans, sum[i]); } } printf("%d\n", ans); } return 0; }