题目大意:
给你一个天平字符串,天平有两个磅秤,天平可以嵌套天平,磅秤的值可以任意修改,问你要使天平平衡最少要修改几个磅秤。

参考文献:https://blog.csdn.net/crazysillynerd/article/details/43876123
思路:因为天平的结构就是一棵二叉树,要使天平平衡则一定需要一个磅秤作为参考,在知道磅秤的重量w和深度下可以求出这个数的总重量=w*pow(2,depth),因为在某个深度下的完全二叉树节点个数=pow(2,edpth)。因为要使天平平衡那么这层深度的节点的重量全部等于w,再乘上个数就是这棵树的总重量。然后用位运算表示就是:总重量=w<<depth。

然后求出每个节点平衡的总重量,那么必然会有一些相等的情况,我们把这写总重量相同的数量计数,也就是说可以得到某个总重量,不需要改变值的数量是w[i],这里用map记录 map[n][w]:表示总重量为w不需要改变n个数,然后我们找到最大多需要改变的数量,用总节点数-最多不需要改变的数量=最少需要改变的数量

代码:

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

/* 3 [[3,7],6] 40 [[2,3],[4,5]] */
typedef long long int ll;
ll sum=0;//统计节点数量 
char str[1500000000];
map<ll,ll>mp;
void dfs(int s,ll t,ll dep){
	if(str[s]=='['){
		int p=0;
		for(ll i=s+1;i<=t;i++){
			if(str[i]=='[')p++;
			if(str[i]==']')p--;
			if(p==0&&str[i]==','){//左右子树的分割,并且保证是从最右子树开始 
				dfs(s+1,i-1,dep+1);//建左子树
				dfs(i+1,t-1,dep+1);//建右子树 
			} 
		}
	}else{
		ll w=0;
		for(ll i=s;i<=t;i++){
			w=w*10+(str[i]-48);//一开始这里写的+=wa了半个小时。。。太粗心了
		}
		++mp[w<<dep];++sum;
	}
}

int main(){
	int t;
	cin>>t;
	while(t--){
		mp.clear();
		cin>>str;
		sum=0;
		dfs(0,strlen(str)-1,0);
		ll maxn=0;
		for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++){
			maxn=max(maxn,it->second);
		}
		cout<<sum-maxn<<endl;
	}
}