CF Edu Binary Search -- pE Equation

方法一 - 解題思路

發現 x 可以是小數，而且可以高達約 1e5，代表 x 的範圍很大。

因為如果某數字 x 符合不等式，比 x 小的數也一定符合。如果 x 不符合，比 x 大的也一定不符合。換句話說，他符合單調性。如果想要列舉 x 看是否符合不等式，可以使用「對答案二分艘」的技巧。

對於一個 x，如果他滿足不等式，代表答案 >= x，否則答案 < x。

方法二 - 解題思路

這題也可以不需要二分搜。

只要一個一個位元枚舉，就可以把原本的時間複雜度壓成 log。

其實這也算是一種二分搜，只是寫法不同罷了。

方法三 - 解題思路

直接用數學把式子爆開

$x^2 + √x = c$ --> $√x = c - x^2$ --> $x = c^2 - 2x^2c + x^4$ 接著直接用四次方公式解爆開即可。（不提供此做法的範例程式碼）

方法一程式碼

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

int main() {
    double c, l = 1, r = 1e5;
    cin >> c;
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if (mid * mid + sqrt(mid) >= c) {
            r = mid;
        }
        else{
            l = mid;
        }
    }
    cout << setprecision(7) << l << "\n";
}

方法二程式碼

#include <bits/stdc++.h>

using namespace std;

int main() {
    double c, cur = 0, ptr = 100000;
    cin >> c;
    while (ptr >= 1e-7) {
        double n = cur + ptr;
        if (n * n + sqrt(n) <= c) {
            cur = n;
        }
        ptr /= 2;
    }
    cout << fixed << setprecision(7) << cur << "\n";
}