UVA-1354 天平难题 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

这道题需要：

1. 遍历二叉树的每种构成方式。我这里每次把当前所有结点列出，然后遍历选取两个组合构成一个新结点，原来的结点剔除，新结点加入。最后只剩一个结点时，就得到二叉树的一种情况。我这里相当于是从叶子结点向上遍历。由于数据量较少，所以我这里没有剪枝。

注意选取两个结点后也对应着两种，A放在左边B放在右边 和 B放在左边A放在右边。

2. 计算宽度时，左侧的宽度除了【左子树的宽度+绳子左侧的长度】之外，右子树的左子树也可能很宽，超过【左子树的宽度+绳子左侧的长度】。因此，要对【右子树的左子树-绳子右侧的长度】和【左子树的宽度+绳子左侧的长度】进行比较，看看谁更长。右侧同理。

#include<stdio.h>
#include<string.h>

int stones[20];
int s;
double r;

double maxWidth;

struct Node {
	bool enable;
	int weight;
	double left, right;
};
Node arr[50];

double max(double a, double b) {
	if(a > b) return a;
	return b;
}

Node mergeNode(int i, int j) {
	Node no;
	no.enable = true;
	no.weight = arr[i].weight + arr[j].weight;
	double a = (double)arr[i].weight / no.weight;
	double b = (double)arr[j].weight / no.weight;
	no.left = max(b + arr[i].left, arr[j].left - a);
	no.right = max(a + arr[j].right, arr[i].right - b);
	return no;
}

void getValue(int len) {
	int i;
	double value;
	for(i = 0; i < len; ++i) {
		if(arr[i].enable) {
			value = arr[i].left + arr[i].right;
			if(value <= r && value > maxWidth) {
				maxWidth = value;
			}
			return;
		}
	}
}

void cal(int len, int enableLen) {
	int i ,j, k;
	if(enableLen == 1) {
		getValue(len);
	}
	for(i = 0; i < len; ++i) {
		if(!arr[i].enable) continue;
		for(j = i + 1; j < len; ++j) {
			if(!arr[j].enable) continue;
			// 二重循环找到一个组合 区分组合在左边和在右边的场景 
			--enableLen;
			arr[i].enable = false;
			arr[j].enable = false;
			arr[len] = mergeNode(i, j);
			cal(len+1, enableLen);
			arr[len] = mergeNode(j, i);
			cal(len+1, enableLen);
			++enableLen;
			arr[i].enable = true;
			arr[j].enable = true;
		}
	}
}

int main() {
	int n, i;
	scanf("%d", &n);
	while(n--) {
		scanf("%lf %d", &r, &s);
		for(i = 0; i < s; ++i) scanf("%d", &stones[i]);
		if(s == 1) {
			printf("%.16lf\n", 0.0);
			continue;
		}

		maxWidth = -1;
		for(i = 0; i < s; ++i) {
			arr[i] = { true, stones[i], 0, 0 };
		}
		cal(s, s);
		if(maxWidth < 0)
			printf("-1\n");
		else
			printf("%.16lf\n", maxWidth);
	}
	return 0;
}