UVA 12166 Equilibrium Mobile

UVA 12166 Equilibrium Mobile

題目概述:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3318

給一個深度不超過16的二元樹，代表一個天平。每根竿子都懸掛在中間，每個秤陀的重量已知。至少修改多少個秤陀的中亮才能讓天平平衡?如題目中的範例圖，把7改成3即可。(參考書上的)
經典入門書p6-46。

思路:

這樣子應該就很明瞭了!其實每個節點重量都已經固定了它的比例關係，上圖紅色的代表葉子(有掛秤陀的)，既然我們知道了他們的比例關係，那我們只要去看看是放大幾倍能符合到的秤陀重量最多，那把全部的秤陀數減去最大符合的秤陀數就是要修改的數量了!!

下面的實作方式是真正把二元樹建出來(其實可以不用，可以參考下面Morris大大的)，然後找出它的深度，再DFS下去把每個葉子的比例關係建好，再利用map計算出每個比例的數量，接著找出哪個比例符合數量最多!

之後看到Morris大大的真的很厲害<(_ _)>

http://morris821028.github.io/2014/10/03/oj/uva/uva-12166/

//By SCJ

//uva 12166

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define maxn 1000000

typedef pair<int,int> pii;

vector<int> G[maxn];

unordered_map<double,int> mp;

int n=0,w[maxn],root,far,leave=0;

void dfs_far(int v,int p,int dep)

{

   far=max(far,dep);

   for(int i:G[v])

   {

       if(i==p) continue;

       dfs_far(i,v,dep+1);

   }

}

void dfs(int v,int p,int x)

{

   if(G[v].size()==1)

   {

       mp[w[v]/(double)x]++;

       leave++;

       return ;

   }

   for(int i:G[v])

   {

       if(i==p) continue;

       dfs(i,v,x/2);

   }

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int T;cin>>T;

   while(T--)

   {

       string s;cin>>s;

       stack<pii> st;

       for(int i=0;i<s.size();++i)

       {

           if(s[i]==','||s[i]=='[') continue;

           else if(s[i]>='0'&&s[i]<='9')

           {

               int tp=0;

               while(i<s.size()&&s[i]>='0'&&s[i]<='9')

               {

                   tp=tp*10+s[i]-'0';++i;

               }

               --i;

               st.push({tp,0});

           }

           else // ==']'

           {

               pii a,b;n++;

               int rt=n;root=rt;

               a=st.top();st.pop();

               b=st.top();st.pop();

               if(a.second) G[rt].push_back(a.first),G[a.first].push_back(rt);

               else ++n,G[rt].push_back(n), G[n].push_back(rt),w[n]=a.first;

               if(b.second) G[rt].push_back(b.first),G[b.first].push_back(rt);

               else ++n,G[rt].push_back(n), G[n].push_back(rt),w[n]=b.first;

               st.push({rt,1});

           }

       }

       if(st.top().second==0)

       {

           cout<<0<<endl;

           continue;

       }

       dfs_far(root,-1,0);

       dfs(root,-1,1<<far);

       int ans=0;

       for(auto i:mp)

       {

           ans=max(ans,i.second);

       }

       cout<<leave-ans<<endl;

       for(int i=0;i<=n;++i) G[i].clear();

       n=far=leave=0;mp.clear();

   }

}

/*

3

[[3,7],6]

40

[[2,3],[4,5]]

*/