AcWing 790. 数的三次方根

题目描述

本题为二分的应用。区间可设为 − 10000 ≤ n ≤ 10000 −10000≤n≤10000 −10000≤n≤10000，这也说明了二分的本质不是单调，而是边界。
首先根据 l l l 和 r r r 的中点 m i d mid mid 处的三次方和 n n n 的大小来选择子区间进行逼近。
这里假设输入为 8 8 8，用图模拟下局部二分过程。

1. 如果 m i d ∗ m i d ∗ m i d ≥ n mid * mid * mid ≥ n mid∗mid∗mid≥n，则说明 m i d ≥ n mid ≥ n mid≥n 的三次方根，则应当在 [ l , m i d ] [l,mid] [l,mid] 的范围内继续逼近，故令 r = m i d r = mid r=mid;
   
2. 如果 m i d ∗ m i d ∗ m i d < n mid * mid * mid < n mid∗mid∗mid

上面两部直至 $r - l < 10^{-8} $时结束(这里有一个问题就是如果结果保留 k k k 位小数，这里就是 1 0 − ( k + 2 ) 10^{-(k+2)} 10−(k+2))。
C++ 代码中保留 n n n 位小数需要加入头文件iomanip，以及 cout << setprecision(n) << std::fixed << ...。

#include 
#include 

using namespace std;

int main()
{
    double n;
    cin >> n;
    
    double l = -10000, r = 10000;
    
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    
    cout << setprecision(6) << std::fixed << l << endl;
}