题解 P1883 【函数】

楼上的方法以三分为主，还有一种判断区间的二分，这里提供另一种二分的思路，对于初学者更好理解。 首先分析F(x)函数，易知仅有一个最低点（否则...模拟退火貌似更好？），设其为x0，则x0左端函数单调递减，x0右端函数单调递增。 换句话说，若当前点在x0左端则当前点函数斜率为负，反之则为正。 至于某一点x斜率的正负，我们仅仅需要算出F(x-Δx)，F(x)，F(x+Δx)的大小关系，根据大小关系二分即可。（即：斜率小于0时向右二分，反之向左二分；若F(x-Δx)>F(x)且F(x)<F(x+Δx)，则x已经极接近最低点了），其中Δx为一个极小值，经验证本题（本做法）Δx不能大于1e-8。 下面是代码 ```cpp #include<cstdio> using namespace std; int n,T; double a[10009],b[10009],c[10009],f1,f2,f3; double f(double x){//计算函数值，直接按题目描述算就行 double max=-1e9-7; for(int i=1;i<=n;i++){ double tmp=a[i]*x*x+b[i]*x+c[i]; if(tmp>max)max=tmp; } return max; } int main(){ scanf("%d",&T); for(int ii=1;ii<=T;ii++){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf%lf%lf",&a[i],&b[i],&c[i]); } double l=0,r=1000,mid=(l+r)/2; f1=f(mid-0.00000001); f2=f(mid); f3=f(mid+0.00000001); while(!((r-l<0.00000001)||((f1>f2)&&(f3>f2)))){//除了常规二分退出条件外，若当前点函数值同时小于左右也要退出 if((f1>f2)&&(f2>f3))l=mid+0.00000001; if((f1<f2)&&(f2<f3))r=mid-0.00000001; mid=(l+r)/2; f1=f(mid-0.00000001); f2=f(mid); f3=f(mid+0.00000001); } printf("%.4lf\n",f2); } return 0; } ```