题目描述
输入输出
思路分析:
- 公式推导:Hi = 2Hi-1 – Hi-2 + 2
(Hi + 1 ) * 2 = Hi-1 + Hi+1 Hi+1 = 2(Hi + 1) – Hi-1 ==> 2Hi - Hi-1 + 2 Hi = 2Hi-1 – Hi-2 + 2
我们已知H1的高度,然后我们可以用二分法,枚举H2的高度.然后推导判断所有的灯是否都没有接触到地面.如果满足则减小H2的高度;如果不满足就增大H2的高度.最后输出B的高度即可.
在二分搜索判断mid是否可行时,如果有高度小于0,由于精度问题不能直接判断小于0,可以设定一个很小的数eps,当该数比eps还要小,说明已经接触到了地面.
参考代码:
#include<iostream> using namespace std; const int inf = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 1006; int N; double A,arr[maxn]; int judge(double x){ arr[1] = x; for(int i = 2;i<N;i++){ arr[i] = 2*arr[i-1] - arr[i-2] + 2; if(arr[i] < eps){ return 0; } } return 1; } int main(){ while(cin>>N>>A){ arr[0] = A; double left = -inf; double right = inf; for(int i = 0;i<100;i++){ // 二分搜索最差 log2 N double mid = (left+right)/2; if(judge(mid)){ right=mid;//因为这个题精度很高,所以每次不用+1 / -1. 直接浮点数 }else{ left=mid; } } printf("%.2llf\n",arr[N-1]); } return 0; }
