原题链接
思路：暴力穷举二叉树(将左右子树用集合表示).(PS:懂了思路并没有什么卵用，研究了半天LRJ大神的代码，自己重写还是写跪了)。
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int maxn=6; struct Tree{ double L,R; Tree():L(0),R(0){} }; double r,w[maxn],sum[1<<maxn]; int n; vector<Tree>tree[1<<maxn]; bool vis[1<<maxn]; void dfs(int root){ if(vis[root]) return; vis[root]=true; bool ok=false;//ok表示是否有孩子结点 for(int left=root&(root-1);left;left=(left-1)&root){ ok=true; int right=root^left; double d1=sum[right]/sum[root]; //距离与重量成反比 double d2=sum[left]/sum[root]; 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[left][i].R-d1,tree[right][j].R+d2); if(t.L+t.R<r) tree[root].push_back(t); } } } if(!ok) tree[root].push_back(Tree()); } int main(){ //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%lf%d",&r,&n); for(int i=0;i<n;i++){ scanf("%lf",&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&(1<<j)) sum[i]+=w[j]; } } int root=(1<<n)-1; fill(vis,vis+(1<<maxn),false); 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); } if(ans<0) printf("-1\n"); else printf("%.12f\n",ans); } return 0; }