UVA 1555 Garland ( 二分 )
UVa Online Judge
移項一下就能得到方程式 h[ i ] = ( h[ i - 1 ] + 1 ) * 2 - h[ i - 2 ],所以只要前兩項確定,後面所有都會跟著唯一確定。前面的項越小,後面的項一定就成關係的一齊變小,所以二分枚舉第二項可不可行就好了。
注意輸出前要再呼叫一次 ok() 函數,因為有可能最後一次是呼叫會小於零直接跳走的那一個 ok( lb )。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const double MAXA = 1e3 + 3; int n; double a; double v[MAXN]; bool ok(double x){ v[ 1 ] = a, v[ 2 ] = x; for(int i = 3; i <= n; ++i){ v[ i ] = ( v[ i - 1 ] + 1 ) * 2 - v[ i - 2 ]; if( v[ i ] < 0.0 ) return false; } return true; } void solve(){ double lb = 0.0, rb = MAXA; for(int i = 0; i < 100; ++i){ double mid = ( lb + rb ) / 2.0; if( ok( mid ) ) rb = mid; else lb = mid; } ok( rb ); printf("%.2lf\n", v[ n ]); } int main(){ while( scanf("%d%lf", &n, &a) == 2 ) solve(); return 0; }