题意:
在一个宽为r 的房间里, 有s个砝码, 每个天平的一端要么挂砝码, 要么挂另一个天平, 并且每个天平要保持平衡。
求使得所有砝码都放在天平上, 且总宽度不超过房间宽度的最大值。
思路:
每个节点只能有两个子节点, 这是一棵二叉树的形式。
通过枚举二叉树的形态, 再枚举每一个叶子节点所放砝码, 最后再计算每个方案的宽度并计算答案。
每增加一个天平, 那么可以放砝码数 + 1。
note:
坑在0的输出了, 用primtf("%.9lf\n", 0)输出来的是0 用0.0来输出才是0.000000 惨wa三发。
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-5
22 #define MAXN 110
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {cout<<x<<endl;}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 double r, ans;
37 double w[MAXN], v[MAXN];
38 double ll[MAXN], rr[MAXN];
39 bool vis[MAXN];
40 int order[MAXN];
41 void read()
42 {
43 scanf("%lf", &r);
44 scanf("%d", &n);
45 for (int i = 1; i <= n; i ++)
46 scanf("%lf", &w[i]);
47 }
48 void get_ans(int u)
49 {
50 memset(ll, 0, sizeof(ll));
51 memset(rr, 0, sizeof(rr));
52 memset(v, 0, sizeof(v));
53
54 for (int i = u; i > 0; i --)
55 {
56 if (order[i] == -1)
57 {
58 int x = i * 2;
59 int y = i * 2 + 1;
60 v[i] = v[x] + v[y];
61 double li = v[y] / v[i];
62 double ri = v[x] / v[i];
63
64 ll[i] = min(-li + ll[x], ri + ll[y]);
65 rr[i] = max(-li + rr[x], ri + rr[y]);
66 }
67 else if (order[i])
68 {
69 v[i] = w[order[i]];
70 }
71 }
72
73 double temp = rr[1] - ll[1];
74 //printf("%.9lf\n", temp);
75 if (temp - r < eps && temp > ans)
76 ans = temp;
77 }
78
79 void dfs(int u, int num, int count)
80 {
81 //printf("%d %d %d\n", u, num, count);
82 if (count == 0)
83 {
84 get_ans(u - 1);
85 return ;
86 }
87 else if (order[u / 2] != -1)
88 {
89 dfs(u + 1, num, count);
90 }
91 else
92 {
93 if (count > num)
94 {
95 order[u] = -1;
96 dfs(u + 1, num + 1, count);
97 order[u] = 0;
98 }
99
100 if (num == 1 && count > 1)
101 return ;
102 for (int i = 1; i <= n; i ++)
103 if (!vis[i])
104 {
105 vis[i] = true;
106 order[u] = i;
107 dfs(u + 1, num - 1, count - 1);
108 order[u] = 0;
109 vis[i] = false;
110 }
111 }
112 }
113 void solve()
114 {
115 memset(vis, false, sizeof(vis));
116 memset(order, 0, sizeof(order));
117 ans = -1;
118 if (n == 1) printf("%.10lf\n", 0.0);
119 else
120 {
121 order[1] = -1;
122 dfs(2, 2, n);
123 printf(ans == -1? "-1\n" : "%.10lf\n", ans);
124 }
125 }
126
127 int main()
128 {
129 int T;
130 scanf("%d", &T);
131 while (T --)
132 {
133 read();
134 solve();
135 }
136 return 0;
137 }