三分

链接

这题可以使用直接求导,然后不断用二分法压缩即可

#include<bits/stdc++.h>
using namespace std;
double f(vector<double>&ss,double x){
    double y=0;
    for(int i=0;i<ss.size();i++){
        y+=ss[i]*pow(x,i);
    }
    return y;
}
int main(){
    int N;double l,r;
    cin>>N>>l>>r;
    vector<double>s(N+1);
    vector<double>ss(N);
    for(int i=0;i<N+1;i++){
        cin>>s[i];
    }
    for(int i=N-1;i>=0;i--){
        ss[N-i-1]=s[i]*(N-i);            
    }
    double ans=0;
    while(abs(r-l)>0.000001){
        double mid=(l+r)/2;
        if(f(ss,mid)<0){
            ans=mid;
            r=mid;
        }
        else{
            ans=mid;
            l=mid;
        }
    }
    cout<<fixed<<setprecision(5)<<ans;
}

当然,我们也可以用三分法

#include<bits/stdc++.h>
using namespace std;
double f(vector<double>& a, double x) {
    double res = 0;
    // 秦九韶算法，更高效且避免 pow 误差
    for(int i = 0; i <= a.size()-1; i++) {
        res = res * x + a[i];
    }
    return res;
}
int main(){
    int N;double l,r;
    cin>>N>>l>>r;
    vector<double>s(N+1);
    for(int i=0;i<N+1;i++){
        cin>>s[i];
    }
    double ans=0;
    while(abs(r-l)>0.0000001){
        double mid1=(2*l+r)/3,mid2=(2*r+l)/3;
        if(f(s,mid1)>f(s,mid2)){
            r=mid2;
            ans=mid2;
        }
        else{
            l=mid1;
            ans=mid1;
        }
    }
    cout<<fixed<<setprecision(5)<<ans;
}