题目链接:https://vjudge.net/contest/210334#problem/G
转载于:https://blog.****.net/todobe/article/details/54171920
题目描述:
给出房间的宽度r和s个挂坠的重量wi,设计一个尽量宽(但宽度不能超过房间宽度r)的天平,挂着所有挂坠。
天平由一些长度为1的木棍组成。木棍的每一端要么挂一个挂坠,要么挂另外一个木棍。如图1所示,设n和m分别是两端的总重量,要让天平平衡,必须满足n*a=m*b。
例如:如果有3个重量分别为1,1,2的挂坠,有3种平衡的天平,如下图所示:
挂坠的宽度忽略不计,且不同的子天平可以相互重叠。如下图所示,宽度为(1/3)+1+(1/4)。
输入格式:
输入第一行为数据组数。每组数据前两行为房间宽度r和挂坠数目s (0 < r < 10,1<=s<=6)。以下s行为一个挂坠的重量wi(1<=wi<=1000)。输入保证不存在天平的宽度恰好在r-10^(-5)和r+10^(-5)(这样可以保证不会出现精度问题)。
输出格式:
对于每组数据,输出最优天平的宽度。如果无解,输出-1。你的输出和标准答案的绝对误差不应超过10^(-8)
题目分析:(搜索)
天平的形态最后可以看成二叉树,所以问题转化成了我们有一堆点(点数还不超过6),要把这一堆点合成一颗树。我们可以用哈弗曼树的想法,每次把两个节点合成一个新的节点,最终只剩下一个节点,就是一组可行解,更新答案。
但是我们不知道每次要合并哪两个点,因为层数很少,所以可以暴力枚举。
这是huffman合并思想
#include<cstdio> #include<iostream> #include <algorithm> using namespace std; struct balance //形象的定义一个带有宽度的'节点',若该节点不是由节点合并而来的,则ls,和rs为0(因为点的左宽和右宽为0),如果是由其他结点合并而来的,则宽度按照实际宽度更新 { double w, ls, rs; balance operator + (const balance c) { balance z; z.w = w + c.w; double l = c.w / (w + c.w); //木棍左边的长度为,右边的点的重量/(两点的重量之和) double r = w / (w + c.w); //同理 z.ls = max(l + ls, c.ls - r); //比较右边点的左边界和左边点的左边界哪个更靠左,因为完全有可能右边点的左边界比左边点的左边界还要靠左 z.rs = max(r + c.rs, rs - l); //同理 return z; } }a[]; double r, ans; int s, T; void dfs(int c) { if (c == s) //n个节点最终加到1个节点只需加n-1次 { ].ls + a[].rs; //利用huffman原理,将树的所有节点最终合成一个'节点',整个天平的宽度即为这个‘节点’的宽度 if (cs <= r && cs>ans) ans = cs; return; } balance b[], d[]; ; i <= s - c + ; i++) b[i] = a[i]; //记录下当前所枚举的各点的情况 ; i <= s - c + ; i++) //这个循环我没弄明白 ; j <= s - c + ; j++) { if (i == j) continue; ; k <= s - c + ; k++) a[k] = b[k]; //重置为刚才用b[]数组记录下的当前c值得情况 ; ; k <= s - c + ; k++) if (k != i && k != j) d[++top] = a[k]; d[++top] = a[i] + a[j]; ; k <= top; k++) a[k] = d[k]; dfs(c + ); } } int main() { scanf("%d", &T); while (T--) { scanf("%lf%d", &r, &s); ; i <= s; i++) { scanf("%lf", &a[i].w); a[i].ls = ; a[i].rs = ; } ans = -; dfs(); printf("%.10lf\n", ans); } ; }
这是枚举子集思想
- &表示交集,^表示差集,|表示并集。
- 利用交集是否为0还可以判断是否存在包含关系。
- 递归枚举
#include<cstdio> #include<cstring> #include<vector> #include <algorithm> using namespace std; struct Tree { double L, R; // distance from the root to the leftmost/rightmost point Tree() :L(), R() {} }; ; << maxn]; << maxn]; vector<Tree> tree[ << maxn]; void dfs(int subset) { if (vis[subset]) return; vis[subset] = true; bool have_children = false;//初始化 )⊂ left; left = (left - )&subset) {//遍历每一种情况,取subset的子集所以要取交集,从上一个的集合再取交集可以提高效率 have_children = true;//进入循环表明有子集 int right = subset ^ left;//得到差集 double d1 = sum[right] / sum[subset];//公示推导出来的 double d2 = sum[left] / sum[subset]; dfs(left); dfs(right); ; i < tree[left].size(); i++) ; 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", &T); while (T--) { scanf("%lf%d", &r, &n); ; i < n; i++) scanf("%lf", &w[i]); ; i < ( << n); i++) {//遍历每一种可能 sum[i] = ; tree[i].clear(); ; j < n; j++) << j)) sum[i] += w[j];//把这个集合中的质量都加起来,包含第j个质量的集合。 } << n) - ;//全部都是1 memset(vis, , sizeof(vis)); dfs(root); ; ; i < tree[root].size(); i++) ans = max(ans, tree[root][i].L + tree[root][i].R);//找到最大值 printf("%.10lf\n", ans); } ; }
2018-04-16