题解 P1883 【函数】

· · 题解

引用1楼

作者: litc 更新时间: 2013-11-06 21:32

“方法二：三分求最值

容易看出，因为a的取值为大于等于0，二次函数的开口向上，所以F(x)的函数图像也是开口向上的，先单调递减再单调递增，于是可以用三分法求二次函数的最值。与二分查找算法类似，先取整个区间的中间值mid=(left+right)/2再取右侧区间的中间值midmid，从而把区间分成三个小区间midmid=(mid+right)/2如果mid比midmid更靠近最值点，我们就舍弃右区间(midmid + 1 ~ end),否则我们就舍弃左区间(left ~ mid - 1).

比较mid与midmid谁更靠近最值，只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时，mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理”

我的方法就是三分求最值

这道题貌似是刘汝佳大佬写在过他的蓝书上的，前面我一直用的while来控制的循环次数，后来看到蓝书上是用for循环来控制的，改了就过了，但确实不知道这个循环次数怎么算的，也不知道为什么写while不过，哪位大佬能告诉我

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int f=1,x=0;
    char ch;
    do
    {
        ch=getchar();
        if(ch=='-') f=-1;
    }while(ch<'0'||ch>'9');
    do
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}
int t;
int n;
int a[10001],b[10001],c[10001];//存储系数
inline double sum(double x)//按题目方式计算f(x)函数
{
    double fx=0;
    for(int i=1;i<=n;i++)
        fx=max(fx,a[i]*x*x+b[i]*x+c[i]);
    return fx;
 }
int main()
{
    t=read();
    for(int i=1;i<=t;i++)
    {
        n=read();
        for(int i=1;i<=n;i++) 
            a[i]=read(),b[i]=read(),c[i]=read();
        double l=0.0,r=10000.0;//三分求最值
        for(int i=1;i<=100;i++)//这个循环次数不知道是怎么算出来的
        {
            double mid1=l+(r-l)/3.0;
            double mid2=(r)-(r-l)/3.0;//三分
            if(sum(mid1)<sum(mid2))/*"先取整个区间的中间值mid=(left+right)/2再取右侧区间的中间值midmid，从而把区间分成三个小区间
midmid=(mid+right)/2如果mid比midmid更靠近最值点，我们就舍弃右区间(midmid + 1 ~ end),否则我们就舍弃左区间(left ~ mid - 1)."--

摘自 litc 的题解 */

            {
                r=mid2;
            }
            else
            {
                l=mid1;
            }
        }
        printf("%.4lf\n",sum(l));
     } 
}