首页 > 代码库 > POJ 1759 Garland（二分答案）
POJ 1759 Garland（二分答案）
【题目链接】 http://poj.org/problem?id=1759
【题目大意】
有n个数字H，H[i]=(H[i-1]+H[i+1])/2-1，已知H[1]，求最大H[n]，
使得所有的H均大于0.
【题解】
我们得到递推式子H[i]=2*H[i-1]+2-H[i-2]，发现H[n]和H[2]成正相关
所以我们只要二分H[2]的取值，同时计算每个H是否大于等于0即可。
【代码】
#include <cstdio>int n;double H[1010],A,B;bool check(double x){ H[1]=A,H[2]=x; for(int i=3;i<=n;i++){ H[i]=2.0*H[i-1]+2-H[i-2]; if(H[i]<0)return 0; }return B=H[n],1;}int main(){ while(~scanf("%d%lf",&n,&A)){ double l=0,r=A; for(int i=0;i<100;i++){ double mid=(l+r)/2; if(check(mid))r=mid; else l=mid; }printf("%.2f\n",B); }return 0;}
POJ 1759 Garland（二分答案）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。