题目描述
递推+二分
Hi = (Hi-1 + Hi+1)/2 - 1 等价于 Hi+1 = 2Hi - Hi-1 + 2
由此可推的公式:
Hi = (i-2) * H2 - (i-1) * H1 + (i-1)*(i-2)
H1是确定的常数,所以这道题其实是要二分H2,Hi和H2有正比关系。
所以,从0到H1来二分H2,确定任意Hi都>=0下,二分得到最小的H2,从而可计算得最小的Hn.
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
const int N=1100;
double h[N];
double x;
int n;
bool check(double mid)
{
if(mid<0) return false;
h[1]=x,h[2]=mid;
for(int i=3;i<=n;i++)
{
h[i]=2*h[i-1]-h[i-2]+2;
if(h[i]<0)
{
return false;
}
}
return true;
}
int main()
{
while(scanf("%d %lf",&n,&x)!=EOF)
{
double l=0,r=x,mid,ans;
for(int i=0;i<100;i++)
{
mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid;
}
else
{
l=mid;
}
}
printf("%.2lf\n",(n-1)*ans-(n-2)*x+(n-2)*(n-1));
}
return 0;
}