1 条题解
-
0
观察题目图像得 函数是一个下凸函数。即对于任意的 ,不存在 ,根据这个定义,我们可以通过三分法求该函数的最值。注:本人的三分法是自己推算来的,效率可能不高,请大家谅解!
随便画出二次函数的一段(二次函数是一个特殊的下凸函数),我们发现一个下凸函数其上四个点无非有以下几种情况:
设下凸函数上四个点横坐标分别为 ,并且我们已经确定该函数的最小值在 之间
若 ,则函数的最小值的 的取值范围一定在 之间,因为根据定义,若有 ,必有 ;
若 ,同理可得,函数最小值的取值范围一定是在 之间。
若 && ,则函数的最小值的x的取值范围一定在 之间,因为下凸函数有且仅有一个低谷,并且下凸函数的最小值在低谷中。
若 && ,同理,函数最小值的取值范围一定在 之间。
最后就只剩下一种情况了,此时函数最小值的取值范围一定在 之间。
由此,我们可以设计出代码(请认真阅读注释):
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=10010; const double inf=2e9; int T,n; double a[maxn],b[maxn],c[maxn],l,r,mid1,mid2,ret,v1,v2,v3,v4; inline double f(double x){ret=-inf;for(int i=0;i<n;i++)ret=max(ret,a[i]*x*x+b[i]*x+c[i]);return ret;}//内置的计算F(x)函数的值的函数 int main() { scanf("%d",&T);//多组数据 while(T--) { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%lf%lf%lf",a+i,b+i,c+i);//读入 l=0;r=1000;//左范围和右范围如题目中所示 while(l+1e-10<r)//这里是为了减小b*x所带来的误差增大化,亦可以写成f(l)+1e-5<f(r) { mid1=(l+l+r)/3;mid2=(l+r+r)/3;//用区间[l,r]的三分点作为分界,每次至少都能使答案范围减小1/3 v1=f(l);v2=f(mid1);v3=f(mid2);v4=f(r);//提前计算出值,避免做重复计算 if(v1<v2)r=mid1; else if(v4<v3)l=mid2; else if(v1>v2&&v2<v3)r=mid2; else if(v4>v3&&v3<v2)l=mid1; else l=mid1,r=mid2;//根据上面分析中得出的公式可得,安排成这样的顺序是为了一次削减尽量多的无用部分,从而加快速度 } printf("%.4lf\n",f(l)); } return 0; }
时间复杂度大约是 ,在题目所允许的时间范围内。本人亲测 ,速度比较快。
- 1
信息
- ID
- 166
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 11
- 已通过
- 8
- 上传者