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

这道题可以转换为求所有数的最大公共前缀

然后就很好解决，维护公共前缀即可，最后求每个数的二进制长度与公共前缀二进制长度的差值即可

我的代码如下

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

map<int, int> len;
int a[N];

void get (int x)
{
	int tmp = x, l = 0;
	while (x)
	{
		l ++;
		x /= 2;
	}
	len[tmp] = l;
}

//求两个数的最大公共前缀
int solve(int l, int a)
{
	get(l);
	get(a);
	
	
	for (int i = 0; i < min(len[l], len[a]); i ++ )
	{
		if (l / (1 << (len[l] - i - 1)) != a / (1 << (len[a] - i - 1)))
		{
			return l / (1 << (len[l] - i));
		}
	}
	
	if (len[l] <= len[a])
	{
		return l;
	}
	else {
		return a;
	}
}

int main() 
{
	int n;
	cin >> n;
	
	int last;
	cin >> last;
	a[0] = last;
	for (int i = 1; i < n; i ++ )
	{
		cin >> a[i];
		last = solve(last, a[i]);
	}
	get(last);
  
	int ans = 0;
	for (int i = 0; i < n; i ++ )
	{
		
		ans += len[a[i]] - len[last];
	}
	
	cout << ans << endl;
	
	return 0;
}