https://www.cnblogs.com/violet-acmer/p/9793209.html
题意:
有N个彩灯关在同一条绳上,给出第一个彩灯的高度A,并给出求解其他彩灯的公式 h[i]=(h[i-1]+h[i+1])/2-1;
求最后一个彩灯的最低高度,并且保证所有的彩灯都不会着地。
题解:
二分第二个彩灯的高度h[2],h[2]越小,h[N]就越小。
证明:
假设最低的彩灯为 i。
由公式可得 h[2] = (h[1]+h[3])/2-1;
有了前两个彩灯的高度,将公式稍加变形,得h[3]=(h[2]+1)*2-h[1].
即,对于 i > 2 ,有 h[i]=(h[i-1]+1)*2-h[i-2];
(1):如果 i == N,则根据公式 h[i]=(h[i-1]+1)*2-h[i-2]; h[2] 越低,则h[3]就越低,近而推出h[4]就越底,当然也就推出 h[N]就越低。
(2):如果 i < N,则有(1)可知,h[2]越低,则h[i-1],h[i]就越低,h[i+1]=(h[i]+1)*2-h[i-1];
如果将h[i]+1中的 +1 去掉,h[i+1]=h[i]*2-h[i-1] => h[i]=(h[i+1]+h[i-1])/2 ,易知,i 为 线段(i-1)(i+1)得中点,此时,h[i]与h[i-1]同步下降,但不会改变h[i+1]得高度
(因为下降后的两点i',(i-1)'与(i+1)构成的三角形与i,(i-1),(i+1)三点构成的三角形相似),但 +1 后,i与(i-1)同时下降,下降的角度相同,但h[i]多个+1,所以h[i+1]就变得越低,则h[N]就会变得越低。
目前还没有能力证出 i < N 时,h[2]越低,则h[N]越低,有大佬会的话还望指点一番%%%%%%%%%
AC代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 #define eps 1e-6 6 const int maxn=1e3+50; 7 8 int N; 9 double A; 10 double h[maxn]; 11 12 bool Check(double x) 13 { 14 h[1]=A,h[2]=x; 15 for(int i=3;i <= N;i++) 16 { 17 h[i]=(h[i-1]+1)*2-h[i-2]; 18 if(h[i] < eps)//注意,此处是与 eps 比较 19 return false; 20 } 21 return true; 22 } 23 24 int main() 25 { 26 scanf("%d%lf",&N,&A); 27 double l=0,r=A; 28 for(int i=1;i <= 100;++i) 29 { 30 double mid=l+((r-l)/2); 31 if(Check(mid)) 32 r=mid; 33 else 34 l=mid; 35 } 36 printf("%.2f\n",h[N]); 37 return 0; 38 }
还有一个疑惑就是,为什么答案不向上取整?
printf()输出的结果是四舍五入的,如果h[N]=10.123,则输出结果为10.12,最后一个彩灯的高度又下降了一些,在下降后为什么就能保证所有的彩灯不着地?