题目大意:
给你一个天平字符串,天平有两个磅秤,天平可以嵌套天平,磅秤的值可以任意修改,问你要使天平平衡最少要修改几个磅秤。
参考文献: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;
}
}