给出房间的宽度r和s个挂坠的重量wi，设计一个尽量宽但小于房间宽度的天平。
如果要使两个重量不同的w1，w2坠在天平两边，就要满足如下等式w1到中点距离为l1=（w2）/（w1+w2），w2到中点距离为l2=（w1）/（w1+w2）；
因为一个天平两臂长度为1(l1+l2=1)，而且根据物理学公式可知w1*(l1)=w2*(l2);
这道题我使用回溯法做，每次枚举两个坠合并成一个坠，那么每次都会使得整个可选的坠的数目减一。
把每个坠都看成一个天平，因此有三个量需要维护：w，l，r（重量，左臂总长，右臂总长），同时在合并两个坠的时候要考虑特殊情况，左边的那个坠右臂特别长，或者右边的那个坠左臂特别长
所以有这么一段：llx=max(a[i].l+l,a[j].l-r); rrx=max(a[j].r+r,a[i].r-l);
#include <iostream> #include <cstdio> using namespace std; struct node { int v; double l,r; }a[10]; double rs,ans;int s; void dfs(node *a,int len) { double llx,rrx,lly,rry,l,r; if(len==2) { l=(a[1].v*1.0)/(a[0].v+a[1].v); r=(a[0].v*1.0)/(a[0].v+a[1].v); llx=max(a[0].l+l,a[1].l-r); rrx=max(a[1].r+r,a[0].r-l); l=(a[0].v*1.0)/(a[0].v+a[1].v); r=(a[1].v*1.0)/(a[0].v+a[1].v); lly=max(a[1].l+l,a[0].l-r); rry=max(a[0].r+r,a[1].r-l); double ans1=llx+rrx; double ans2=lly+rry; if(ans<ans1&&ans1<rs) ans=ans1; if(ans<ans2&&ans2<rs) ans=ans2; return; } struct node c[10]; for(int i=0;i<len;i++) c[i]=a[i]; for(int i=0;i<len;i++) { for(int j=0;j<len;j++) { if(i==j) continue; l=(a[j].v*1.0)/(a[i].v+a[j].v); r=(a[i].v*1.0)/(a[i].v+a[j].v); llx=max(a[i].l+l,a[j].l-r); rrx=max(a[j].r+r,a[i].r-l); int tmp=a[i].v+a[j].v; int top=0; for(int k=0;k<len;k++) { if(k==i||k==j) continue; a[top++]=c[k]; } a[top].v=tmp;a[top].l=llx;a[top++].r=rrx; if(llx+rrx>rs) { for(int k=0;k<len;k++) a[k]=c[k]; continue; } dfs(a,top); for(int k=0;k<len;k++) a[k]=c[k]; } } } int main() { int T; for(scanf("%d",&T);T;T--) { scanf("%lf%d",&rs,&s); for(int i=0;i<s;i++) { scanf("%d",&a[i].v); a[i].l=a[i].r=0; } if(s==1) {printf("%.8f ",0.0);continue;} ans=0; dfs(a,s); ans==0?puts("-1"):printf("%.16f ",ans); } return 0; }