二分查找之——P1883函数

作者:admin|日期:2019-02-12|热度:

题目描述


给定n个二次函数f1(x),f2(x),...,fn(x)(均形如ax^2+bx+c),设F(x)=max{f1(x),f2(x),...,fn(x)},求F(x)在区间[0,1000]上的最小值。
原题链接:https://www.luogu.org/problemnew/show/P1883

解题思路:


因为a>=0,所以二次函数是一条开口向上的抛物线,当a=0时退化成一次函数,也就变成一条直线,如下图。因此,可以把F(x)函数也近似看成一条开口向上的抛物线,二分查找的时间无法根据中点的大小来确定该往哪边继续查找,应该根据中点的倾斜趋势来决定查找区间,即:如果右边值更小,那么最小值一定在右边,反之在左边。

注意:判断倾斜趋势可以采用在中点的右边再取一点,根据两点的值来确定,但两点距离一定要非常非常小(1e-8以上),否则0分。
另外:此题默认测试数据很奇葩,竟然x和F(x)的值完全相同,一开始没注意看题,直接输出x,结果0分。
二分查找之-91883函数

参考代码:


#include <bits/stdc++.h>
using namespace std;

int n;
double a[10005],b[10005],c[10005];

double fx(double x){
double ans,max;
max=a[0]*x*x+b[0]*x+c[0];
for(int i=1;i<n;i++){
ans=a[i]*x*x+b[i]*x+c[i];
if(ans>max) max=ans;
}
return max;
}

bool judge(double x){
double f1,f2;
f1=fx(x);
f2=fx(x+0.000000001);
return f1>f2;
}
double findx(double left,double right){
double mid=(left+right)/2;
if(abs(right-left)<1e-10) return left;
if(judge(mid)) return findx(mid,right); //右边更小
else return findx(left,mid);
}
int main(){
int T;
double x;
cin>>T;
for(int i=0;i<T;i++){
cin>>n;
for(int j=0;j<n;j++){
cin>>a[j]>>b[j]>>c[j];
}
x=findx(0,1000);
printf("%.4f",fx(x));
cout<<endl;
}
return 0;
}