0w1

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;
}