2010年1月31日星期日.ural1066-pku1759
一道二分的題目
由題目中的遞推式可以很容易的導出
H[i+1] = 2 * H[i] + 2 - H[i-1]
然后我們可以二分枚舉H[2]的值，判斷是否成立，并且更新B值即可。
1
2 const double eps = 1e-8;
3 const int inf = 0x7fffffff;
4 //http://m.shnenglu.com/schindlerlee
5 double B;
6 int n;
7 bool judge(double H1,double H2,int idx)
8 {
9 double H3 = 2*H2+2-H1;
10 if (H3 < 0) { return false; }
11 if(idx == n) {
12 B = min(B,H3);
13 return true;
14 }
15 return judge(H2,H3,idx + 1);
16 }
17
18 int main()
19 {
20 B = inf;
21 double A;
22 int i,j,k;
23 scanf("%d %lf",&n,&A);
24 double left = 0,right = A;
25 while (left + eps < right) {
26 double mid = (left + right) / 2;
27 if(judge(A,mid,3)) {
28 right = mid;
29 }else {
30 left = mid;
31 }
32 }
33 printf("%.2f\n",B);
34 return 0;
35 }
36
37