一元三次方程求解

【TimeGate】

https://www.luogu.org/problem/P1024

【解题思路】

因为区间很大，所以可以二分。 三个答案都在[-100,100]范围内，两个根的差的绝对值>=1,保证了每一个大小为1的区间里至多有1个解，
也就是说当区间的两个端点的函数值异号时区间内一定有一个解，
同号时一定没有解。那么我们可以枚举互相不重叠的每一个长度为1的区间，在区间内进行二分查找。

【code】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;  6 double a,b,c,d;  7 int x;  8 float x1,x2,xx;  9 double f(double x){ 10     return (a*x*x*x+b*x*x+c*x+d); 11 } 12 int main(){ 13     //freopen("1403.in","r",stdin); 14     //freopen("1403.out","w",stdout); 
15     scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 16     b=b/a; 17     c=c/a; 18     d=d/a; 19     a=1.0; 20     for (x=-100;x<=100;x++){ 21         x1=x; 22         x2=x+1; 23         if (f(x1)==0) 24             printf("%.2lf ",x1); 25         else
26             if (f(x1)*f(x2)<0){ 27                 while (x2-x1>=0.001){ 28                     xx=(x1+x2)/2; 29                     if (f(x1)*f(xx)<=0) x2=xx; 30                     else x1=xx; 31  } 32                printf("%.2lf ",x1); 33  } 34  } 35      return 0; 36 }