算法题目——二次函数三分求极值(HDU-3714）

桃扇骨 2022-09-14 02:22 151阅读 0赞

题目链接：[HDU-3714][]

题目描述：  
对于N个二次函数，求每个二次函数的最小值中的最大值  
思路：  
使用三分法求极值（递归调用）  
对于这种在指定区间里只有一个极值点的函数（凸函数凹函数都可以），我们可以使用三分法求极值

三分极值法的思想：对于区间\[l,r\]，令m=(l+r)/2即中点，再令mm=(m+r)/2，即右半段的中点。这样l,m,mm,r四个点就把区间分成了三份。

此时若m更靠近极值点，则令r=mm。否则令l=m；这样就把区间缩小了。  
对于用float类型表示的连续函数，可以设定一个迭代次数size，例如可以取size=100。当运行了100次之后差不多就能取到极值点了

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_9_color_FFFFFF_t_70_g_se_x_16]

//题目：HDU 3714
    //时间：2021/9/30
    //作者：lfs
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    #include<vector> 
    using namespace std;
     
    const double eps=1e-9;
    const double MIN=0;
    const double MAX=1000;
    double p[10000+10][3];
    int n;
     
    double Calc(double a)
    {
        
        double ans=-1e20;
    	for(int i=0;i<n;i++)
    	{
        
    		ans=max(ans,a*a*p[i][0]+a*p[i][1]+p[i][2]);
    	}
    	return ans;
    }
    double Solve()
    {
        
    	//三分
        double Left, Right;
        double mid, midmid;
        double mid_value, midmid_value;
         Left = MIN; Right = MAX;
        while (Left + eps < Right)
        {
        
            mid = (Left + Right) / 2;
            midmid = (mid + Right) / 2;
            mid_value = Calc(mid);
            midmid_value = Calc(midmid);
     
            if (mid_value <= midmid_value) 
    			Right= midmid;
            else 
    			Left = mid;
        }
    	return midmid_value;
    }
    int main() 
    {
        
    	// freopen("in.txt","r",stdin);
        int T;
    	scanf("%d",&T);
    	vector<double> vec;
    	while(T--)
    	{
        
    		scanf("%d",&n);
    		for(int i=0;i<n;i++)
    			scanf("%lf %lf %lf",&p[i][0],&p[i][1],&p[i][2]);
     
    		vec.push_back(Solve());
    	}
    	for(auto i:vec)
    	{
        
    		printf("%.4lf\n",i);
    	}
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]

[HDU-3714]: https://acm.hdu.edu.cn/showproblem.php?pid=3714
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8a83306ed93548059498113d29313556.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f00840e7cb1f4a4f8dae20889b1249d1.png