poj 1759 Garland 二分搜索

题意：

有n个灯泡，给出第一个灯泡的高度h1和n，求第n个灯泡hn的最小值。所有灯泡满足Hi = (H_i-1 + H_i+1)/2 - 1, for all 1 < i < N ，Hi >= 0, for all 1 <= i <= N。

分析:

所求hn与h2有单调关系，直接二分枚举h2。

代码：

//poj 1759
//sepNINE
#include <iostream>
#include <cmath>
using namespace std;
double a;
int n;
int dbl(double x)
{return fabs(x)<1e-9?0:(x>0?1:-1);
}
double getans(double x)
{double tmp;double x1=a;double x2=x;for(int i=3;i<=n;++i){tmp=2*x2+2-x1;if(dbl(tmp)>=0){x1=x2;x2=tmp;}else{tmp=-1;break;}}	return tmp;
}
int main()
{scanf("%d%lf",&n,&a);double l=0;double mid,t,h=a;while(h-l>1e-8){mid=(l+h)/2;t=getans(mid);if(dbl(t+1)==0)l=mid;elseh=mid;}printf("%.2lf\n",getans(h)+1e-9);return 0;	
}