题解 | #游游的除2操作#

设 表示为前 个数全取到 的最少操作次数。因为数组存不下，但是最多要存的数也就 个，实际上更少，所以这里可以采用 unordered_map，且每个数只能从上一个数能取到的转移过来，如果上一个数取不到 那么也就没必要转移了，最后就看 的最小值即可。

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<int> a(n);
	for (int i = 0; i < n; i ++) {
		cin >> a[i];
	}

	vector<unordered_map<int, int>> dp(n);

	for (int i = 30; i >= 0; i --) {
		auto x = a[0] >> i;
		if (!dp[0].count(x)) {
			dp[0][x] = i;
		} else {
			dp[0][x] = min(dp[0][x], i);
		}
	}

	for (int i = 1; i < n; i ++) {
		for (int j = 30; j >= 0; j --) {
			auto x = a[i] >> j;
			if (dp[i - 1].count(x)) {
				if (!dp[i].count(x)) {
					dp[i][x] = dp[i - 1][x] + j;
				} else {
					dp[i][x] = min(dp[i - 1][x] + j, dp[i][x]);
				}
			}
		}
	}

	int ans = INT_MAX;
	for (auto [_, num] : dp[n - 1]) {
		ans = min(ans, num);
	}

	cout << ans << "\n";

	return 0;
}