题目描述

题目大意&链接

给定一个浮点数 n ，求它的三次方根（结果保留6位小数）。

输入输出样例：
输入：

1000.00

输出：

10.000000

详情：ac_790数的三次方根

解题思路

这题就是简单的二分，有两个地方需要注意。

小数的精度 eps 需要在给定的精度上 +2 来确保结果的准确性：
const double eps = 1e-8;

确定 left 和 right 的初值，当 n >= 0 时，right 至少 >=1；当 n < 0 时，left 至少 <= -1：

// 根据n的正负设置初始区间
if (n >= 0) {
    left = 0, right = max(1.0, n);  // 处理n < 1的正数
} else {
    left = min(n, -1.0), right = 0;  // 处理n > -1的负数
}

完整代码

#include<iostream>

using namespace std;

double n;

bool check(double x)
{
    if((x * x * x) >= n) return true;
    else return false;
}

double bsearch_3(double l, double r)
{
    //结果精确到小数点后6位，则eps要开6+2=8位
    const double eps = 1e-8;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    
    return l;
}


int main()
{
    scanf("%lf", &n);
    double left, right;
    
    // 根据n的正负设置初始区间
    if (n >= 0) {
        left = 0, right = max(1.0, n);  // 处理n < 1的正数
    } else {
        left = min(n, -1.0), right = 0;  // 处理n > -1的负数
    }
    
    double res = bsearch_3(left, right);
    printf("%.6lf", res);
    return 0;
}

时间和空间复杂度

时间复杂度：O(logn)
空间复杂度：O(1)