题解：UVA1555 Garland

Big_Yi · 2024-07-14 07:32:05 · 题解

upd on October 12, 2024：之前的代码忽略了有多组数据的问题、可能存在精度不准的问题等，现在的代码保证 AC。

二分查找

主要就是根据

变形得到

然后就只要保证

即可。

因为 H_1=A，根据公式可以选择二分第二个点的高度，范围是 0 到一个比较大的值，比如说 10000000，或者 inf，多循环几次以增加精度。

最后附上代码。

#include<bits/stdc++.h>
using namespace std;
double h[10005];
int n;
double a;
double b;
bool judgemid(double mid){
  h[1]=a;
    h[2]=mid;
    for(int i=3;i<=n;i++){
        h[i]=2*h[i-1]-h[i-2]+2;
        if(h[i]<0.000001){//精度问题，一般不能直接和0比较
            return 0;//上升
        }
    }
    b=h[n];
    return 1;//下降
}
int main(){
    while(cin>>n>>a){
        double left=0.0,right=1000000.0,mid;
        for(int i=0;i<=1009;i++){
            mid=left+(right-left)/2;//防超出范围
            if(judgemid(mid))right=mid;
            else left=mid;
        }
        printf("%.2f\n",h[n]);//保留两位小数
    }
    return 0;
}