P1024 [NOIP 2001 提高组] 一元三次方程求解——题解

解题思路

由于根之间至少相差 1，可以枚举每个长度为 1 的区间 $[i,i+1]$。若端点函数值为 0，端点就是根；若两端异号，则区间内有一个根，使用二分法不断缩小区间。收集三个根后排序并按两位小数输出。

复杂度分析

只检查 200 个单位区间，每个根二分固定约 80 次，时间与空间复杂度都可视为 $O(1)$。

易错点

要避免整数根在相邻区间中被重复记录，并注意把非常接近 0 的结果输出为 0.00。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
double a,b,c,d;
double f(double x){return ((a*x+b)*x+c)*x+d;}
int main(){
    cin>>a>>b>>c>>d;vector<double> roots;
    for(int i=-100;i<100&&roots.size()<3;i++){
        double l=i,r=i+1,fl=f(l),fr=f(r);
        if(fabs(fl)<1e-8){if(roots.empty()||fabs(roots.back()-l)>1e-5)roots.push_back(l);}
        if(fl*fr<0){
            for(int k=0;k<80;k++){double mid=(l+r)/2;if(f(l)*f(mid)<=0)r=mid;else l=mid;}
            double x=(l+r)/2;if(roots.empty()||fabs(roots.back()-x)>1e-5)roots.push_back(x);
        }
    }
    if(roots.size()<3&&fabs(f(100))<1e-8) roots.push_back(100);
    sort(roots.begin(),roots.end());
    cout.setf(ios::fixed);cout<<setprecision(2);
    for(int i=0;i<3;i++) cout<<(fabs(roots[i])<0.0005?0.0:roots[i])<<(i==2?'\n':' ');
    return 0;
}

#include <bits/stdc++.h> using namespace std; double a,b,c,d; double f(double x){return ((a*x+b)*x+c)x+d;} int main(){ cin>>a>>b>>c>>d;vector roots; for(int i=-100;i<100&&roots.size()<3;i++){ double l=i,r=i+1,fl=f(l),fr=f(r); if(fabs(fl)<1e-8){if(roots.empty()||fabs(roots.back()-l)>1e-5)roots.push_back(l);} if(flfr<0){ for(int k=0;k<80;k++){double mid=(l+r)/2;if(f(l)*f(mid)<=0)r=mid;else l=mid;} double x=(l+r)/2;if(roots.empty()||fabs(roots.back()-x)>1e-5)roots.push_back(x); } } if(roots.size()<3&&fabs(f(100))<1e-8) roots.push_back(100); sort(roots.begin(),roots.end()); cout.setf(ios::fixed);cout<<setprecision(2); for(int i=0;i<3;i++) cout<<(fabs(roots[i])<0.0005?0.0:roots[i])<<(i==2?'\n':' '); return 0; }