例题6-9 UVa839-Not so Mobile
程序员文章站
2024-03-18 23:30:16
...
依然还是尝试使用基于指针的树来解决,本来已经过了uDebug,但还是遇到了无限RE。第一次RE后,换到Dev c++进行调试,发现是旧标准下内存申请的问题(具体原因我也讲不清),缝缝补补终于调到Dev c++也没问题后继续submit,但还是RE。最终也没找到问题。但还是记录下代码。
题目链接:UVa 839
修改得面目全非的RE代码:
#include <iostream>
//#include <fstream>
using namespace std;
struct Node {
int data, distance;
Node* left, * right;
Node() : data(0), distance(0), left(NULL), right(NULL) {}
}*root;
void remove(Node* u) {
if (u == NULL) return;
remove(u->left);
remove(u->right);
delete u;
}
int build(Node*& u) {
u = new Node();
int wl, dl, wr, dr;
while (cin >> wl >> dl >> wr >> dr) {
if (wl == 0 || wr == 0) {
if (wl == 0) {
u->left = new Node(); //必须先申请内存,不然会“Program received signal SIGSEGV, Segmentation fault”
int n = build(u->left); //这里不加中间变量也会同上,用dev调试发现不加中间变量时无法赋值
u->left->data = n;
}
if (wr == 0) {
u->right = new Node();
int n = build(u->right);
u->right->data = n;
}
u->left->distance = dl;
u->right->distance = dr;
}
else {
u->left = new Node();
u->right = new Node();
u->left->data = wl;
u->left->distance = dl;
u->right->data = wr;
u->right->distance = dr;
}
int n = u->left->data + u->right->data;
return n;
}
}
bool is_balance(Node* u) { //判断是否平衡
if (u->left != NULL && u->right != NULL) { //叶子结点没有子树
if (u->left->data * u->left->distance != u->right->data * u->right->distance)
return false;
if (!is_balance(u->left)) return false;
if (!is_balance(u->right)) return false;
}
return true;
}
int main() {
int T, cnt = 0;
//ofstream out("C:\\Users\\Acer\\Desktop\\1.txt");
cin >> T;
while (T--) {
build(root);
//if (out.is_open()) {
if (cnt++)
cout << endl;
if (is_balance(root))
cout << "YES" << endl;
else
cout << "NO" << endl;
//}
remove(root);
}
return 0;
}
紫书代码(简洁易懂):
#include <iostream>
using namespace std;
bool is_balance(int& w) {
int wl, dl, wr, dr;
bool b1 = true, b2 = true;
cin >> wl >> dl >> wr >> dr;
if (!wl) b1 = is_balance(wl);
if (!wr) b2 = is_balance(wr);
w = wl + wr;
return b1 && b2 && (wl * dl == wr * dr);
}
int main() {
int T, cnt = 0;
cin >> T;
while (T--) {
int w;
if (cnt++)
cout << endl;
if (is_balance(w))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
上一篇: 分数化小数(decimal)