1.题目描述：点击打开链接
2.解题思路：本题要求求出若干条抛物线在给定的区间[0,1000]内的最小值。根据F(x)的定义可以发现，它的形状仍然是下凸的，因此可以利用三分搜索(ternary search)解决。三分搜索的思想是：如果F(x)是一个下凸函数，，取区间[L,R]的两个三分点m1,m2，比较F(m1)和F(m2)的大小，如果F(m1)<F(m2)，那么最值在区间[L,m2]，否则在区间[m1,R]。注意：不要弄错缩减后的区间端点！另外，本题的迭代次数的上限是通过实验得出的，比赛中可以多尝试几个值，如果答案不正确，就加大次数；如果超时，就减少次数。如果这两种方法都行不通，那么就将终止条件改为区间长度小于阈值。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 10000+10int n, a[N], b[N], c[N];double F(double x){double ans = a[0] * x*x + b[0] * x + c[0];for (int i = 1; i < n; i++)ans = max(ans, a[i] * x*x + b[i] * x + c[i]);//根据F(x)的定义，取所有函数值的最大值return ans;}int main(){//freopen("t.txt", "r", stdin);int T;cin >> T;while (T–){cin >> n;for (int i = 0; i < n; i++)scanf("%d%d%d", &a[i], &b[i], &c[i]);double L = 0, R = 1000.0;for (int i = 0; i < 100; i++)//本题的100次是实验得出的{double m1 = L + (R – L) / 3;double m2 = R – (R – L) / 3;if (F(m1) < F(m2))R = m2;else L = m1;}printf("%.4lf\n", F(L));}return 0;}
只是微笑地固执自己的坚持，
