欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

例题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;
	}
}