第一道：poj 1905Expanding Rods

題意：兩道墻（距離L）之間架一根棒子，棒子受熱會變長，彎曲，長度變化滿足公式（?s=(1+n*C)*L），求的是彎曲的高度h。

首先來看這個圖：

如圖，藍(lán)色為桿彎曲前，長度為L

紅色為桿彎曲后，長度為s

h是所求。

又從圖中得到三條關(guān)系式;

（1）?????? 角度→弧度公式? θr = 1/2*s

（2）?????? 三角函數(shù)公式? sinθ= 1/2*L/r

（3）?????? 勾股定理? r^2 – ( r – h)^2 = (1/2*L)^2

?

把四條關(guān)系式化簡可以得到

?

?

逆向思維解二元方程組：

要求（1）式的h，唯有先求r

但是由于（2）式是三角函數(shù)式，直接求r比較困難

因此要用順向思維解方程組：

在h的值的范圍內(nèi)枚舉h的值，計算出對應(yīng)的r，判斷這個r得到的(2)式的右邊? 與 左邊的值S的大小關(guān)系? （ 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 else 24 high=mid; 25 } 26 printf("%.3lf\n",mid); 27 } 28 return 0; 29 }

第二題：poj 3122?Pie

題意：f+1個人分n個派。

要求：每個人的派的體積一樣大且盡量最大，每個人的派必須來自同一個派。

二分題，千萬要注意，輸入的是朋友的數(shù)量f，分pie是分給所有人，包括自己在內(nèi)共f+1人

下界low=0，即每人都分不到pie

上界high=maxsize，每人都得到整個pie，而且那個pie為所有pie中最大的

對當(dāng)前上下界折中為mid，計算"如果按照mid的尺寸分pie，能分給多少人"

求某個pie（尺寸為size）按照mid的尺寸，能夠分給的人數(shù)，就直接size / mid，舍棄小數(shù)就可以

?

看代碼：

#include<stdio.h> #include<string> #include<math.h> #include<string.h> #include<algorithm> #define pi 3.14159265359 #define esp 1e-6 using 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;elselow=mid;}printf("%.4lf\n",mid*pi);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/PJQOOO/p/4250814.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的两道二分coming~的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。