题解：UVA1476 Error Curves

fish_love_cat · 2025-11-28 21:50:25 · 题解

NOIP 考前复习。

最终的函数其实就是一大堆二次函数整在一起取最大，由于保证每一个二次函数都有 a>0，分讨容易证明这个是单谷函数。

于是考虑三分然后暴力 check。

时间复杂度 O(n\log V)，其中 V 是值域。

什么是三分？

都叫考前复习了还是写一下的好。

我们设目前的区间是 [l,r]，其中 m_1 和 m_2 分别是该区间的两个三等分点。

• 当 f(m_1)<f(m_2) 时，若谷底在 (m_2,r] 显然违反单谷的限制，于是可以令 r\gets m_2。
• 当 f(m_1)\ge f(m_2) 时，若谷底在 [l,m_1) 显然违反单谷的限制，于是可以令 l\gets m_1。

当 r-l<\text{eps} 时就跑路，精度够了。

于是做完了。

#include<bits/stdc++.h>
#define inf 10000000000
#define eps 0.000000001
using namespace std;
int n,a[10005],b[10005],c[10005];
double check(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;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i]>>b[i]>>c[i];
    double l=0,r=1000;
    while(r-l>eps){
        double mid1=(l*2+r)/3;
        double mid2=(l+2*r)/3;
        if(check(mid1)<check(mid2))r=mid2;
        else l=mid1;
    }
    printf("%.4lf\n",check(l));
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 缇亚忒见状，就大致明白了状况。她轻轻露出理解的笑容，像是想起什么般翻找军服的小袋子。
// 然后掏出一件小东西。
//「这个给你。」

// 那是一个中央镶著美丽蓝色宝石，设计非常可爱的小胸针。