UVA-12166 天平性质+字符处理

          这题思维难度很大，关键是总结这个性质。

  1.天平性质：某个秤砣重量为w，高度为h，如果要让这个天平平衡并且以这个秤砣为基准，那么整个天平的总重量为w*(2^h)

  2.利用这个性质：题目要求秤砣数量改变最少，就是说尽量多的不改变秤砣重量，把总质量作为主键，统计总质量相同的秤砣个数，

最后计算出数量最多的，就是不用改变质量的最大秤砣数量，用所有秤砣数减去不用改变质量的最大秤砣数量就是答案。

  3.当然，用这个性质，会让某些秤砣的质量变为小数。

  4.注意，总重量可能会变成long long类型。

AC代码：

#include<cstdio>#include<cstring>#include<map>using namespace std;#define max(x,y) (x) > (y) ? (x) : (y)typedef long long LL;const int maxn = 1e6 + 5;char str[maxn];map<LL, int>ha;int node; //numbers of nodevoid dfs(int l, int r, int h){    if(str[l] == '[') {        int p = 0;        for(int i = l + 1; i < r ; ++i){            if(str[i] == '[') ++p;            else if(str[i] == ']') --p;            else if(str[i] == ',' && p == 0) {                dfs(l + 1, i - 1, h + 1); //Left                dfs(i + 1, r - 1, h + 1); //Right            }        }    }    else {        ++node;        int num = 0;        while(l <= r) num = num * 10 + str[l++] - '0';        ha[(LL)num << h]++;    }}int main(){    int T;    scanf("%d", &T);    while(T--) {        node = 0;        scanf("%s", str);        int n = strlen(str);        dfs(0, n-1, 0);        int ans = 0;        for(map<LL, int>::iterator c = ha.begin(); c != ha.end(); ++c) {            ans = max(ans, c->second);        }        PRintf("%d/n",node - ans);        ha.clear();    }    return 0;}如有不当之处欢迎指出！