关于三分

RT，题解区里面的代码和我最开始学的都是用的

lmid=l+\frac{r-l}{3}

写的，而 oiwiki 里面用的是

lmid=mid-\epsilon

写的，第二种方法本质上好像是在二分斜率。

但是我本地测试下来如果

\epsilon

过大会导致死循环，过小会导致答案错误，求助我的代码哪里有问题。另外，如果是整数三分的话，是不是只要保证

r-l>2

，使用第一种写法就不会有问题？

CPP

#define eps 1e-10
using namespace std;
const int maxn = 1e4+5;
int n , a[maxn] , b[maxn] , c[maxn];
double calc(double x)
{
	double res = -1e18;
	rep(i , 1 , n)res=max(res , a[i]*x*x+b[i]*x+c[i]);
	return res;
}
void Solve()
{
	cin >> n;
	rep(i , 1 , n)cin >> a[i] >> b[i] >> c[i];
	double l = 0 , r = 1000;
	while(fabs(l-r) > eps)
	{
		double mid = (l+r)/2;
		double lmid = mid-eps , rmid = mid+eps;
		if (calc(lmid) > calc(rmid))l=lmid;
		else r=rmid;
	}
	printf("%.4lf\n" , calc(l));
	return;
}

讨论操作

回复

相关推荐

关于三分