UVa 12166 - Equilibrium Mobile

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

給一個天平表達式，請問至少要調整幾個權重才能使之平衡。

Sample Input

3
[[3,7],6]
40
[[2,3],[4,5]]

Sample Output

1
0
3

Solution

恰好是一棵二元樹，那麼可以得知道假使一個權重不改，最後的天平重量為何。
假使 depth 上的權重 w 不改，則最後的天平重量就是 w * pow(2, depth)。

藉此，可以記錄所有最後的天平重量，得知最多有多少不改 = N - 最少改變個樹。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;

char exp[1048576];
map<long long, int> R;
void dfs(int l, int r, int dep) {
    if (exp[l] == '[') {
        int p = 0;
        for (int i = l + 1; i <= r - 1; i++) {
            if (exp[i] == '[')	p++;
            if (exp[i] == ']')	p--;
            if (p == 0 && exp[i] == ',') {
                dfs(l+1, i-1, dep+1);
                dfs(i+1, r-1, dep+1);
            }
        }
    } else {
        int w;
        exp[r+1] = '\0';
        sscanf(exp+l, "%d", &w);
        R[(long long)w<<dep]++;
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", exp);
        R.clear();
        dfs(0, strlen(exp) - 1, 0);
        int sum = 0, mx = 0;
        for (map<long long, int>::iterator it = R.begin();
            it != R.end(); it++)
            sum += it->second, mx = max(mx, it->second);
        printf("%d\n", sum - mx);
    }
    return 0;
}
/*
3
[[3,7],6]
40
[[2,3],[4,5]]
*/