POJ 1759 - Garland

http://poj.org/problem?id=1759

概要

N 個のランプを取り付ける． 一番左のランプを高さ A に取り付けると決めたときに，一番左側のランプの高さ B の最小値を答える．

左から i 番目のランプの高さ H[i] は，左右のランプの高さ H[i-1], H[i+1] から

H[i] = (H[i-1] + H[i+1])/2 - 1

と決められる．また，どのランプも地面の下になってはならない．つまり

for all 1 <= i <= N, H[i] >= 0

である．

制約

• 3 <= N <= 1000
• 10 <= A <= 1000

解法

H[2] が増えると B = H[N] も増え，逆に H[2] が減ると H[N] も減るので，H[2] に関して H[i] >= 0 の条件を守るように二分探索すればよい．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 pair<double, bool> f(int N, double h0, double h1)
 6 {
 7   for (int i = 2; i < N; i++) {
 8     double h = 2*h1 - h0 + 2;
 9     if (h < 0) {
10       return make_pair(0, false);
11     }
12     h0 = h1;
13     h1 = h;
14   }
15   return make_pair(h1, true);
16 }
17 
18 int main()
19 {
20   int N;
21   double A;
22   scanf("%d %lf", &N, &A);
23 
24   double lo = 0.0, hi = 1e10;
25   double ans = 1e10;
26   for (int i = 0; i < 200; i++) {
27     const double mid = (lo + hi)/2.0;
28     const pair<double,bool> r = f(N, A, mid);
29     if (r.second) {
30       ans = min(ans, r.first);
31       hi = mid;
32     } else {
33       lo = mid;
34     }
35   }
36   printf("%.2f\n", ans);
37   return 0;
38 }