luogu 1024 一元三次方程求解

· · 题解

课堂例题1： luogu1024 答案在[-100,100]范围内，两个根的差的绝对值>=1,故每一个大小为1的区间里至多有1个解。

这是一个0011模型的题，我们利用二分法不断接近零点，所求得的极小区间就是出现的第一个1即l就是我们想要的答案。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define maxn 500010
const double eps=1e-4;  //相当于定义一个精度常量0.0001 

double a,b,c,d,l,r,mid;

double f(double x){  //原方程 
    return x*x*x*a+x*x*b+x*c+d;
}

int main(){
    cin>>a>>b>>c>>d;
    for(int i=-100;i<=100;++i){  //枚举根所在的区间 
        l=i;  //左区间l-mid 
        r=l+1;  //右区间mid-r 
        if(f(l)==0){  //找到零点 
            printf("%.2f ",l);
            continue;
        }
        if(f(l)*f(r)<0){//满足二分条件 
            while(r-l>eps){//卡精度用的 
                mid=(l+r)/2;
                if(f(mid)*f(r)<=0) l=mid;  //如果mid-r满足二分条件，说明答案在此区间，将左区间更新至mid继续查询 
                else r=mid;  //如果l-mid满足条件，就将右区间更新至mid 
            }
            printf("%.2f ",l);  //在这个0011模型中第一个出现的1即为所求 
        }
    }
    return 0;
}