UVA 12166 Equilibrium Mobile-白红宇

UVA 12166 Equilibrium Mobile

阅读量：6440 次

发布时间：2019-06-23

本文共 1019 字，大约阅读时间需要 3 分钟。

题意：

　　给出数个天平，每个天平的结构都类似于二叉树，只有左右重量都相等时才平衡，求每个天平最少改多少个秤砣，也就是叶子结点可以使得整个天平平衡。天平的深度不超过16。

分析：

　　要使得改动的数量最少，那么就至少有一个秤砣不变，然后以这个秤砣为基准来调整整个天平。天平的结构是二叉树，那么由此我们可以得出，如果以深度为d重量为w的秤砣为基准，那么整个天平的重量就是w * pow(2, d)，即w << d。当然，可能会有一些秤砣算出的以各自为基准的天平总重量相同，设天平总重量为sum，那么这些秤砣的数量就表示了如果使天平的总重量为sum，需要使多少个秤砣保持不变。用map<long long,int>a，表示以a[i]为基准需要改动多少个。

代码：

#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         using namespace std; map
         
          a; int sum; string line; void dfs(int d,int s,int l) { if(line[s]=='[') { int p=0; for(int i=s+1;i!=l;++i) { if(line[i]=='[') ++p; if(line[i]==']') --p; if(p==0&&line[i]==',') { dfs(d+1,s+1,i-1); dfs(d+1,i+1,l-1); } } } else { long long w=0; for(int i=s;i<=l;++i) w=w*10+line[i]-'0'; ++sum,++a[w<
          
           >T; while(T--) { cin>>line; a.clear(); sum=0; dfs(0,0,line.size()-1); int maxn=0; map
           
            ::iterator it; for(it=a.begin();it!=a.end();it++) maxn=max(maxn,it->second); cout<
            
             <

转载于:https://www.cnblogs.com/137033036-wjl/p/4890031.html

你可能感兴趣的文章