题解 P1768 【天路】

2018-10-31 12:33:53


谈一下这道题的二分方式。

实数二分主要有两种形式。

1. 判断 l,reps 的关系

while (r - l >= eps) {
    double mid = (l + r) / 2;
    // ...
}

2. 直接二分 $100$ 次

for (int times = 0; times < 100; ++i) {
    double mid = (l + r) / 2;
    // ...
}

通常,第二种的精度是要比第一种高的。

如果采用第二种方式进行二分的话,你可能会说:诶?怎么 TLE 了?

所以要把二分次数缩小一些。缩小到多少合适呢?

仔细读题,发现:「保证答案在 $200$ 以内。」 「保留 $1$ 位小数。」。既然要保留一位小数,那么我们需要计算到百分位。又因为答案保证不高于 $200$,所以总共只有 $\frac{200}{\frac{1}{100}}=20000$ 种可能的输出。$\lceil \log_220000\rceil = 15$(即 $2^{14}=16384,2^{15}=32768$),所以只需要二分 $15$ 次就可以得出结果了:

double l = 0, r = 200; 
for (int i = 0; i < 15; ++i) {
    double mid = (l + r) / 2; 
    if (check(mid)) l = mid; 
    else r = mid;
}