P1024 一元三次方程求解

因为精度要求很小，所以有一个暴力的想法就是枚举区间内公差很小的一个等差数列然后判断。

公差取太小时要判重。

code:

#include<bits/stdc++.h>
using namespace std;
#define Db double
const Db eps=1e-3;
Db a,b,c,d;
inline bool check(Db x)
{
	return fabs(x*x*x*a+x*x*b+x*c+d)<eps;
}
int main()
{
	Db i;
	cin>>a>>b>>c>>d;
	cout<<fixed<<setprecision(2);
	for(i=-100.0;i<=100;i+=1e-4)
	if(check(i)&&!check(i-1e-4))cout<<i<<' ';
	return 0;
}

考虑优化。发现根与根之差的绝对值大于等于 (1) 这个条件没有利用。有了这个条件我们发现相邻两个整数之间（不包含端点）最多有一个根。

于是可以先判掉整数然后在区间内有根的两个相邻整数之间二分。

代码就不放了，因为懒得写了

时间复杂度都是 (O(1))（（（