首页 > 代码库 > uva1354 天平难题 解题报告
uva1354 天平难题 解题报告
uva1354 天平难题。主要有 回溯法，二叉树模拟。
当然，这道题也有很多剪枝，但是这个用二叉树性质模拟的数组应该过了，这样写，这道题，完全就足够了。
原题目链接：https://uva.onlinejudge.org/external/13/1354.pdf
题目大意：
就是首先给你一个房间的宽度r，之后有s个挂坠，第i个挂坠的重量是wi，设计一个尽量宽，但是不能宽过房间.的天平。当然会有好几组这样的数据。
这些天平棍的长度都为1，天平棍要么挂 挂坠，要么就继续挂木棍设挂的木棍必须要让天平平衡，满足n＊a＝＝m＊b。这就是个物理概念。
其它东西，题目里写的很清楚。
而这道题整体思想就是 1，枚举二叉树。2，计算宽度。
枚举二叉树，很显然用到的是dfs＋回溯。
二叉树的模型，主要就用的是这个东西来枚举 like根＝＝i子节点＝＝ i＊2，i＊2+1，这样的。
从第二个点开始枚举。其中dfs（num，sit，use）
num：代表这个节点编号，
sit：现在这棵树中有多少位置可供填写。
use：现在有use个挂件还可以用。
PS:枚举的时候还要注意，每次进到一个新点的时候要判断父亲节点是不是天平棍，－1为棍，如果不是棍，就＋＋，找下一个节点。
计算宽度的时候，从最后一个点开始往前递推。设以这个节点为0，左边就是负长度，而右边就是正长度。这就很好的解释了其中
l[i]=min(-L+l[x],R+l[y]);
r[i]=max(-L+r[x],R+r[y]);
这段代码的意思。
1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 double val[10],l[105],r[105],w[10],ans,room; 6 int n,t[105],visit[105]; 7 int judge(int x) 8 { 9 memset(l,0,sizeof(l));10 memset(r,0,sizeof(r));11 memset(val,0,sizeof(val));12 for(int i=x;i;i--)13 {14 if(t[i]==-1){ //是天平棍，对它的子节点进行处理。15 int x=i*2,y=i*2+1;16 val[i]=val[y]+val[x];17 double L=val[y]/val[i];18 double R=val[x]/val[i];19 l[i]=min(-L+l[x],R+l[y]);20 r[i]=max(-L+r[x],R+r[y]);21 }22 else if (t[i])//或者是挂件。只计量挂件的重量就行了。23 {24 val[i]=w[t[i]];25 }26 }27 double a=r[1]-l[1];28 if(a-room<1e-5)ans=max(ans,a);29 }30 int DFS(int num,int sit,int use)31 {32 if(use==0){//所有的挂件都放完了，开始计算长度。33 judge(num-1);34 return 0;35 }36 if(t[num/2]!=-1){//父亲节点不是棍子，就不能往下放东西。37 DFS(num+1,sit,use);38 }39 else40 {41 if(use>sit){//挂件要比位置多，创位置。42 t[num]=-1;43 DFS(num+1,sit+1,use);44 t[num]=0;45 }46 if(sit==1&&use>1) return 0;47 for(int i=1;i<=n;i++)48 {49 if(!visit[i]){50 visit[i]=1;51 t[num]=i;52 DFS(num+1,sit-1,use-1);//放挂件53 visit[i]=0;54 t[num]=0;55 }56 }57 }58 }59 int main()60 {61 int tot;62 scanf("%d",&tot);63 while(tot--)64 {65 scanf("%lf%d",&room,&n);66 memset(w,0,sizeof(w));67 memset(t,0,sizeof(t));68 memset(visit,0,sizeof(visit));69 for(int i=1;i<=n;i++)70 scanf("%lf",&w[i]);71 ans=-1;72 t[1]=-1; //第一个根就是个棍。73 if(n==1){74 printf("%.10lf\n",0.0);75 }76 else {77 DFS(2,2,n);//从节点2开始枚举。刚好就只有2个位置。78 if(ans==-1)printf("-1\n");79 else printf("%.10lf\n",ans);80 }81 }82 return 0;83 }
uva1354 天平难题 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。