洛谷 P1883 函数

---

P1883 函数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Error Curves - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这两题是一模一样的，过一题水两题。

分析

主要难点在于证明F(x)是一个单峰函数可以被三分，但是我随便画了几个f(x)之后发现好像就是可以被三分，而且a也大于0，那就直接开做了。

坑

题目要求答案精度是精确到1e-4，还要求四舍五入那就是要求答案精确到1e-5。

但是我们三分的时候一直在缩小的是x的取值，x进入f(x)之后才是答案的值。

如果有这么一个二次函数他峰值变化及其缓慢，而x的值变的较快，那三分x的值就必须比答案更加精确。

具体的值不知道怎么算（函数太难了），但是留个心眼，给三分的值开到两倍多的精度也许就够了。

AC代码

#include <bits/stdc++.h>
//#define int long long
#define fr first
#define se second
#define endl '\n'
using namespace std;const int N=1e4+5;
int n;
double a[N],b[N],c[N],l,r,mid,eps=1e-10;double cul(double x){double MAX=a[1]*x*x+b[1]*x+c[1];for(int i=2;i<=n;++i)MAX=max(MAX,a[i]*x*x+b[i]*x+c[i]);return MAX;
}void solve(){cin>>n;for(int i=1;i<=n;++i)cin>>a[i]>>b[i]>>c[i];while(r-l>eps){mid=(l+r)/2;if(cul(mid)>cul(mid+eps))l=mid;else r=mid;}cout<<fixed<<setprecision(4)<<cul(l)<<endl;
}void init(){l=0,r=1000;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin>>t;while(t--)init(),solve();return 0;
}