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");elseprintf("%.16lf\n", maxWidth);}return 0;
}