【C++】「一本通 1.2 例 3」曲线

【来源】

一本通题库-1435
LibreOJ-10013
vjudge

【题目描述】

明明做作业的时候遇到了 $n$n 个二次函数 $S_i(x)=ax^2+bx+c$Si​(x)=ax2+bx+c，他突发奇想设计了一个新的函数 $F(x)=\max \{S_i(x)\},i=1…n$F(x)=max{Si​(x)},i=1…n。

明明现在想求这个函数在 $[0,1000]$[0,1000] 的最小值，要求精确到小数点后四位，四舍五入。

【输入格式】

输入包含 $T$T 组数据，每组第一行一个整数 $n$n；

接下来 $n$n 行，每行 $3$3 个整数 $a, b, c$a,b,c ，用来表示每个二次函数的 $3$3 个系数。注意：二次函数有可能退化成一次。

【输出格式】

每组数据输出一行，表示新函数 $F(x)$F(x) 的在区间 $[0,1000]$[0,1000] 上的最小值。精确到小数点后四位，四舍五入。

【样例输入】

2
1
2 0 0
2
2 0 0
2 -4 2

【样例输出】

0.0000
0.5000

【数据范围】

对于 $50\%$50% 的数据，$1≤n≤100$1≤n≤100；

对于 $100\%$100% 的数据，$1≤T≤10, 1≤n≤10^5, 0≤a≤100, 0≤|b|≤5000, 0≤|c|≤5000$1≤T≤10,1≤n≤105,0≤a≤100,0≤∣b∣≤5000,0≤∣c∣≤5000。

【解析】

三分。
三分法是在二分查找的基础上，在右区间（或左区间）再进行一次二分。

与二分查找不同的是，三分法所面向的搜索序列的要求是：序列为一个凸性函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足不严格单调递增（递减），右侧序列必须满足不严格单调递减（递增）。

首先把 l-r 这个区间分成三部分（lmid和rmid）。
接下来就是判断，我们因为要求最小值，所以我们要使得左边的值尽可能的小，这样最左边就是最小的。
接下来就是判断最大值，就是找出lmid和rmid判断出来的最大值，判断如果lmid的最大值大于rmid，那就说明当前的队列不是左边最小，就把l移到lmid的位置，跳过不符合的那一段。如果小于，那就把r移到rmid的位置，在更左边寻找。
经过这一循环的运算之后，我们就可以得到一个递增的序列，而这个序列的最左边就是最小值。
答案：判断出l的值就好了。

细节：精度要开小，我开了1e-12。

【代码】

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

#define RI                 register int
#define re(i,a,b)          for(RI i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)<(b)) ? (a):(b))

using namespace std;

typedef long long LL;

const int N=1e5+5;
const int inf=2e9;

int n,T;
double a[N],b[N],c[N];

double calc(double x) {
    double ret=-inf;
    for(int i=1; i<=n; i++) 
        ret=MAX(ret,a[i]*x*x+b[i]*x+c[i]);
    return ret;
}

int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i=1; i<=n; i++) 
            scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
        double l=0,r=1000;
        while(r-l>1e-12) {
            double lmid=l+(r-l)/3.0;
            double rmid=r-(r-l)/3.0;
            if(calc(lmid)<=calc(rmid)) r=rmid;
                else l=lmid;
        }
        double ans=calc(l);
        printf("%0.4lf\n",ans);
    }
    return 0;
}