题解 UVA12166 【修改天平 Equilibrium Mobile】

安静学习 · 2019-02-17 17:53:40 · 题解

这道题可以看成一个二叉树，每一个砝码其实就是叶子节点

每次以其中一个砝码来作为基准，进行一个天平的构建

每一次以一个叶子结点作为基准修改的话， 当前天平的重量可以表示为 砝码重量*(2,当前深度)

也有可能出现比较特殊的情况（例如样例中给出的非完全二叉树），所以要找出来每一个修改后天平重量出现的最多次数maxn，用总的叶子结点sum

得到答案sum-maxn

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
string a;
int maxn,sum;
map <long long,int> cnt;

void bfs(int first,int last,int depth){
    if(a[first] == '['){
        int flag = 0;
        for(int i = first + 1;i <= last;i++){
            if(a[i] == '['){flag++;}
            if(a[i] == ']'){flag--;}
            if(a[i] == ',' && !flag){
                bfs(first+1,i - 1,depth+1);
                bfs(i + 1,last - 1,depth + 1);
            }
        }
    }
    else{
        sum++;
        long long test = 0;
        for(int i = first;i <= last;i++){
            test = test * 10 + (a[i] - '0');
        }
        cnt[test << depth]++;
        maxn = max(maxn,cnt[test << depth]);
    }
}

int main(){
    int t = 0;
    while(cin >> t){
        for(int i = 0;i < t;i++){
            cin >> a;
            sum = 0;
            cnt.clear();
            maxn = 0;
            bfs(0,a.length() - 1,0);
            cout << sum - maxn << endl;
        }
    }
    return 0;
}