UVA839 Not so Mobile 天平 解题报告

题目链接

https://vjudge.net/problem/UVA-839

题目大意

输入一个树状天平，根据力矩相等原则判断是否平衡。如图6-5所示，所谓力矩相等，就是WlDl=WrDr，其中Wl和Wr分别为左右两边砝码的重量，D为距离。

采用递归（先序）方式输入：每个天平的格式为Wl，Dl，Wr，Dr，当Wl或Wr为0时，表示该“砝码”实际是一个子天平，接下来会描述这个子天平。当Wl=Wr=0时，会先描述左子天平，然后是右子天平。

解题思路

这道题输入就采用了先序递归的方式，所以在实现的时候也可以采取先序递归的方式接收输入。
判断的过程显然可以用递归，比较方便，先判断左子树（左子天平），然后判断右子树（右子天平），最后判断整个天平，这显然是后序遍历顺序。
其实我们无需显式建树，隐式建树即可。先序建树后序判断同时进行。判断结果的布尔值通过函数返回值返回，力矩值通过引用变量传出。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define endl '\n';
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1e9 + 7;

bool isBalance(int &w) {    // 无需显式建树，隐式建树即可。先序建树后序判断同时进行。
    int w1, d1, w2, d2;
    cin >> w1 >> d1 >> w2 >> d2;
    bool b1 = true, b2 = true;
    if (!w1)
        b1 = isBalance(w1);
    if (!w2)
        b2 = isBalance(w2);
    w = w1 + w2;
    return b1 && b2 && (w1 * d1 == w2 * d2);
}

void solve() {
    int w;
    if (isBalance(w))
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    int Case = 1;
    cin >> Case;
    while (Case--) {
        solve();
        if (Case)
            cout << "\n";
    }
    return 0;
}