寒假专题1-H.Error Curve

Error Curve

题意：对于二次函数，ax^2+bx+c，给定n组a，b，c（均>0），求出[0,1000]范围内所有二次函数组成的最大图像的最小值

思路：经过分析可以发现，对于该图像，当一个个二次函数的最大图像开始叠加，变化的图像一定比原来的图像高，并且这是一个连续的图像！所以，整个图像一定存在着一个最小值且仅有一个最小值！所以，我们采用三分的方法来求这个最值点。

代码：

#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define debug(x) cout<<"------"<=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(0);
typedef pair PII;
typedef vector  VI;
const int mod = 1e9+7;
const int INF =0x3f3f3f3f;
const int N=10001;
const double eps=1e-15;
int n;
int a[N],b[N],c[N];
double cur(double x)
{
	double ans=-INF;
	rep(i,1,n)
	{
		ans=max(ans,a[i]*x*x+b[i]*x+c[i]);	
	}
	return ans;	
} 
void solve()
{
	cin>>n; 
	rep(i,1,n)
	{
		cin>>a[i]>>b[i]>>c[i];	
	}
	double l=0.0,r=1000.0,lmid,rmid;
	double tmpl,tmpr;
	 while(l+epstmpr) l=lmid;
		else
		{
			r=rmid;	
		}  
	 }
	 printf("%.4f\n",cur(r));
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

几个注意的点

三分 主要用于查找 凸函数和凹函数的极值

const double eps = 1e-8;

double f(double x) { ... } //计算函数f(x)的值

double l = 0, r = 1e8;
while (r - l > eps) {
    double ml = l + (r - l) / 3;
    double mr = r - (r - l) / 3;
    
    double a = f(ml), b = f(mr);
    //当是极大值的时候，每次要舍去小的那部分区间
    if (a < b) l = ml;	
    else r = mr;
    //当求的值为极小值时，每次要舍去的是大的那部分区间
    if (a < b) r = ml;
    else l = ml;
}
寒假集训专题一

相关

寒假集训专题一-J.最大连续和

标签