武汉ACM集训——二分和尺取-2武汉ACM集训——二分和尺取-2

157 阅读 0 评论 104 点赞

我是靠谱客的博主火星上小刺猬，这篇文章主要介绍武汉ACM集训——二分和尺取-2武汉ACM集训——二分和尺取-2，现在分享给大家，希望可以做个参考。

武汉ACM集训——二分和尺取-2

Acwing 790 数的三次方根

题解

典型二分答案题型。

从答案推初始条件，由于是浮点数，while 内判断条件为 r - l >= 1e-7。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    double n;
    scanf("%lf", &n);
    double l = -10000, r = 10000;
    // 二分判断条件 r - l >= 1e-7 时，可认为 r != l，否则认为 r == l。
    while (r - l >= 1e-7)
    {
        double md = (l + r) / 2.0;
        // md 的三次方
        double tmp = pow(md, 3);
        // tmp 小于等于 n 时，则 md 过小，因此 l 增大
        if (tmp <= n)
            l = md;
        // tmp 大于 n时，则 md 过大，因此 r 增大
        else if (tmp > n)
            r = md;
    }
    printf("%lf", l);
    return 0;
}