Uva 12166 该死的天平又不平衡了

一、题意

输入kase组数据，每组包括一个字符串，表示一个天平，如 "[[3,7],6]"
要求输出一个数，表示最少需要修改多少个数字使得天平平衡。

二、解析

逻辑思维题。实际上整个天平中，任意一个数字都能决定整个天平的所有数字（因为要使得天平平衡），这样一来，就可以计算所有叶子结点所最终确定出的平衡天平总重量，统计每一种重量的数量，数量中最大的那一个所对应的叶子节点就是我们不要变的，这样只需要修改剩下的叶子即可。

三、代码

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <cctype>
#include <cmath>
using namespace std;
using LL = long long;
int kase, leafNum;
map<LL, int> cnt;

void solve(string str, int depth) {
    int in = 0, pos = -1;
    for(int i = 0; i < str.size(); i ++){
        char ch = str[i];
        if(ch == '[') in ++;
        else if(ch == ']') in --;
        else if(ch == ',' && in == 1) {
            pos = i;
            break;
        }
    }
    if(pos == -1) {
        int val = stoi(str);
        cnt[val * pow(2, depth)] ++;
        leafNum ++;
    }
    else {
        solve(str.substr(1, pos - 1), depth + 1);
        solve(str.substr(pos + 1, str.size() - pos - 2), depth + 1);
    }
}

int main() {
    cin >> kase;
    while(kase --) {
        leafNum = 0, cnt.clear();
        string str;
        cin >> str;
        solve(str, 0);
        int max_cnt = 0;
        for(auto p : cnt) max_cnt = max(max_cnt, p.second);
        cout << leafNum - max_cnt << endl;
    }
}

四、归纳

• 逻辑思维题。想不到就很难，想到了的话编码还是挺快的。

第二次做还是没想到.....我是不是没救了 orz