首页 > 代码库 > 两道二分coming~
两道二分coming~
第一道：poj 1905Expanding Rods
题意：两道墙（距离L）之间架一根棒子，棒子受热会变长，弯曲，长度变化满足公式（ s=(1+n*C)*L），求的是弯曲的高度h。
首先来看这个图：
如图，蓝色为杆弯曲前，长度为L
红色为杆弯曲后，长度为s
h是所求。
又从图中得到三条关系式;
（1） 角度→弧度公式 θr = 1/2*s
（2） 三角函数公式 sinθ= 1/2*L/r
（3） 勾股定理 r^2 – ( r – h)^2 = (1/2*L)^2
把四条关系式化简可以得到
逆向思维解二元方程组：
要求（1）式的h，唯有先求r
但是由于（2）式是三角函数式，直接求r比较困难
因此要用顺向思维解方程组：
在h的值的范围内枚举h的值，计算出对应的r，判断这个r得到的(2)式的右边 与 左边的值S的大小关系 （ S= (1+n*C)*L ）
很显然的二分查找了。。。。。
看代码：
1 #include<stdio.h> 2 #include<string> 3 #include<math.h> 4 #include<string.h> 5 #include<algorithm> 6 #define esp 1e-5 7 using namespace std; 8 int main() 9 {10 double l,n,c,s,h,r;11 while(scanf("%lf%lf%lf",&l,&n,&c)!=EOF)12 {13 if(l==-1&&n==-1&&c==-1)14 break;15 s=(1+n*c)*l;16 double low=0.0,high=l*0.5,mid;17 while(high-low>esp)18 {19 mid=(low+high)/2;20 r=(4*mid*mid+l*l)/(8*mid);21 if(2*r*asin(l/(2*r))<s)22 low=mid;23 else24 high=mid;25 }26 printf("%.3lf\n",mid);27 }28 return 0;29 }
第二题：poj 3122 Pie
题意：f+1个人分n个派。
要求：每个人的派的体积一样大且尽量最大，每个人的派必须来自同一个派。
二分题，千万要注意，输入的是朋友的数量f，分pie是分给所有人，包括自己在内共f+1人
下界low=0，即每人都分不到pie
上界high=maxsize，每人都得到整个pie，而且那个pie为所有pie中最大的
对当前上下界折中为mid，计算"如果按照mid的尺寸分pie，能分给多少人"
求某个pie（尺寸为size）按照mid的尺寸，能够分给的人数，就直接size / mid，舍弃小数就可以
看代码：
#include<stdio.h>#include<string>#include<math.h>#include<string.h>#include<algorithm>#define pi 3.14159265359#define esp 1e-6using namespace std;int main(){ int t; int n,f,maxs; double v; double r[10001]; double s[10001]; scanf("%d",&t); while(t--) { maxs=0.0; int ans=0; scanf("%d%d",&n,&f); f++; for(int i=0;i<n;i++) { scanf("%lf",&r[i]); s[i]=r[i]*r[i]; if(maxs<s[i]) maxs=s[i]; } double low=0.0,high=maxs,mid; while(high-low>esp) { mid=(low+high)/2; ans=0; for(int i=0;i<n;i++) { ans+=(int)(s[i]/mid); } if(ans<f) high=mid; else low=mid; } printf("%.4lf\n",mid*pi); } return 0;}
两道二分coming~
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。