Not so Mobile UVA 839
输入一个树状天平,根据力矩相等原则判断是否平衡。如图6-5所示,所谓力矩相等,就是WlDl=WrDr,其中Wl和Wr分别为左右两边砝码的重量,D为距离。采用递归(先序)方式输入:每个天平的格式为Wl,Dl,Wr,Dr,当Wl或Wr为0时,表示该“砝码”实际是一个子天平,接下来会描述这个子天平。当Wl=Wr=0时,会先描述左子天平,然后是右子天平。
样例输入:
1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2
样例输出:
YES
测试提交的网址:https://vjudge.net/problem/UVA-839
题目分析:
- 类似于二叉树,当Wl等于0时,说明有左子树;当Wr等于0时,说明有右子树;而当Wl和Wr同时为0时,说明有左右两个子树
- 采用递归方式,使用引用传值。
递归:
源代码
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;
//输入一个子天平,返回子天平是否平衡,参数W为子天平的总重量
bool solve(int& W)
{
int W1, D1, W2, D2;
cin >> W1 >> D1 >> W2 >> D2;
bool b1 = true, b2 = true;
if(!W1) //如果w1=0,说明有左子树
b1 = solve(W1); //判断左子树是否平衡
if(!W2) //如果w2=0,说明有右子树
b2 = solve(W2); //判断右子树是否平衡
W = W1 + W2; //当前子天平的总重量
return b1 && b2 && (W1*D1 == W2*D2);
}
int main()
{
int T, W;
cin >> T;
while(T--)
{
if(solve(W))
cout << "YES" << endl;
else
cout << "NO" <<endl;
if(T)
cout << endl;
}
return 0;
}