1. Title
2. Question meaning
gives the width of the room
r
r
r and
s
s
The weight of s pendants
w
i
w_i
wi?. Design a space as wide as possible (but the width should not exceed the width of the room)
r
r
r) balance with all the pendants hanging from it.
The balance consists of some wooden sticks of length 1. At each end of the stick hang either a pendant or another stick. As shown in Figure 7-9, suppose
n
n
n and
m
m
m is the total weight hung at both ends respectively. To balance the balance, it must satisfy
n
?
a
=
m
?
b
n*a=m*b
n?a=m?b.
For example, if there are three pendants with weights 1, 1, and 2 respectively, there are three kinds of balanced scales, as shown in Figure 7-10.
The width of the pendant is ignored, and different subscales can overlap each other. As shown in Figure 7-11, the width is
(
1
/
3
)
+
1
+
(
1
/
4
)
(1/3) + 1 + (1/4)
(1/3) + 1 + (1/4).
Enter the number of data sets in the first line. The first two lines of each set of data are room widths
r
r
r and the number of pendants
s
s
s(
0
<
r
<
10
0 For each set of data, output the width of the optimal balance. If there is no solution, output -1. The absolute error between your output and the standard answer should not exceed 10-8.
3. Analysis
If both the pendant and the wooden stick are used as nodes, then a balance corresponds to a binary tree. As given in the question, the three balances with pendants 1, 1, and 2 are shown in Figure 7-12.
For a deterministic binary tree, the exact position of each pendant can be calculated, and then the width of the entire balance can be calculated. Therefore, the core task of this question is: Enumerating the binary tree.
How to enumerate a binary tree? The most intuitive method is to use the backtracking method framework, selecting two nodes each time to form a subtree, and recursively
s
?
1
s-1
s?1 layer is enough. Taking four pendants 1, 1, 2, and 3 as an example, the following is part of the solution tree (not all subtrees of each node are drawn), as shown in Figure 7-13.
The above method is sufficient to solve this problem, but there is still room for optimization because some binary trees are enumerated multiple times (such as the two thick-framed nodes in Figure 7-13).
The recommended enumeration method is: Top-down construction. Each time the left subtree is enumerated which subset is used, the right subtree will use the remaining subset.
4. Code implementation
// UVa1354 Mobile Computing
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
struct Tree {<!-- -->
double L, R; // distance from the root to the leftmost/rightmost point
Tree():L(0),R(0) {<!-- -->}
};
const int maxn = 6;
int n, vis[1<<maxn];
double r, w[maxn], sum[1<<maxn];
vector<Tree> tree[1<<maxn];
void dfs(int subset) {<!-- -->
if(vis[subset]) return;
vis[subset] = true;
bool have_children = false;
for(int left = (subset-1) & amp;subset; left; left = (left-1) & amp;subset) {<!-- -->
have_children = true;
int right = subset^left;
double d1 = sum[right] / sum[subset];
double d2 = sum[left] / sum[subset];
dfs(left); dfs(right);
for(int i = 0; i < tree[left].size(); i + + )
for(int j = 0; j < tree[right].size(); j + + ) {<!-- -->
Tree t;
t.L = max(tree[left][i].L + d1, tree[right][j].L - d2);
t.R = max(tree[right][j].R + d2, tree[left][i].R - d1);
if(t.L + t.R < r) tree[subset].push_back(t);
}
}
if(!have_children) tree[subset].push_back(Tree());
}
int main() {<!-- -->
int T;
scanf("%d", & amp;T);
while(T--) {<!-- -->
scanf("%lf%d", & amp;r, & amp;n);
for(int i = 0; i < n; i + + ) scanf("%lf", & amp;w[i]);
for(int i = 0; i < (1<<n); i + + ) {<!-- -->
sum[i] = 0;
tree[i].clear();
for(int j = 0; j < n; j + + )
if(i & amp; (1<<j)) sum[i] + = w[j];
}
int root = (1<<n)-1;
memset(vis, 0, sizeof(vis));
dfs(root);
double ans = -1;
for(int i = 0; i < tree[root].size(); i + + )
ans = max(ans, tree[root][i].L + tree[root][i].R);
printf("%.10lf\
", ans);
}
return 0;
}