和二分非常类似的一个算法，与二分不同的是
二分是单调的，而三分是一个先增后减或者先减后增
三分可以求出峰值。
注意三分一定是严格单调的，不能有相等的情况。
不过貌似只有求函数最值才用到这个东西，没有二分应用范围那么广。
画画图可以发现，满足先减后增
图和雅礼集训里Merchant那道题非常的像，只不过那道题是最大值，可以用二分。
这道题是最小值，用三分
#include#define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 1e5 + 10;double a[MAXN], b[MAXN], c[MAXN];int n;double f(double x){ double res = -1e9; REP(i, 0, n) res = fmax(res, a[i] * x * x + b[i] * x + c[i]); return res;} int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &n); REP(i, 0, n) scanf("%lf%lf%lf", &a[i], &b[i], &c[i]); double l = 0, r = 1e3; while(r - l > 1e-11) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if(f(m1) > f(m2)) l = m1; else r = m2; } printf("%.4lf\n", f(l)); } return 0;}
这道题我主要是推公式推了好久，我一直算错……
首先可以分两种情况
（1）有影子在墙上
（2）没有影子在墙上
没有影子在墙上的时候，通过计算可以得出当光线照在墙角的时候最大。
设人到墙的距离为x
这个时候我们可以得到x的上界h * D / H（相似）
这个时候就可以合并到第一种情况。
第一种情况可以推出影子长度L = x + (D * h - x * H) / (D - x)
不需要化简，只要在程序中可以算出就行了。
这个时候我就猜测，肯定在某个x是最大的。
我就把x等于各种值得情况打印了出来。
果然，有个最值。
那么就三分 。
可以看到，三分的应用是在有浮点数的题目中求最值。
#include#define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;double H, h, D;inline double f(double x){ return x + (D * h - x * H) / (D - x);} int main(){ int T; scanf("%d", &T); while(T--) { scanf("%lf%lf%lf", &H, &h, &D); double l = 0, r = h / H * D; while(r - l > 1e-11) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if(f(m1) > f(m2)) r = m2; else l = m1; } printf("%.3lf\n", f(l)); } return 0;}
这是一道省选题。
首先我先观察题目可以发现一个性质。
路径必然是从AB上走一段然后走到CD某个点上然后走到D
首先确定了AB上的一点可以用三分算出最优解
然后我就猜测AB上的点也可以用三分做。
然后就这么做了。
经过长时间的调试。
70分。
然后我就遇到了一些奇怪的问题
sqrt里面要加上EPS，不然相同的点一算为0，浮点数可能弄到负数。10分。
然后我是用参数方程写的，比较复杂，中间有个地方写错了，20分
AC了之后看别人题解发现可以同时维护x坐标的mid和y坐标的mid，且是一一对应的。
我用参数方程就复杂了，思维量和代码量都上升了。
但我懒得改了。
#include#define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const double EPS = 1e-8;struct node{ double x, y; void read() { scanf("%lf%lf", &x, &y); }}a, b, c, d;double p, q, r;double cos1, sin1, cos2, sin2;inline double dis(node a, node b){ return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + EPS);}double f(double t1, double t2){ node k1 = node{a.x + t1 * cos1, a.y + t1 * sin1}; node k2 = node{c.x + t2 * cos2, c.y + t2 * sin2}; return dis(a, k1) / p + dis(k1, k2) / r + dis(k2, d) / q;}double f1(double t){ double l = 0, r = dis(c, d); while(r - l > EPS) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if(f(t, m1) > f(t, m2)) l = m1; else r = m2; } return f(t, l);} int main(){ a.read(); b.read(); c.read(); d.read(); scanf("%lf%lf%lf", &p, &q, &r); cos1 = (b.x - a.x) / dis(a, b); sin1 = (b.y - a.y) / dis(a, b); cos2 = (d.x - c.x) / dis(c, d); sin2 = (d.y - c.y) / dis(c, d); double l = 0, r = dis(a, b); while(r - l > EPS) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if(f1(m1) > f1(m2)) l = m1; else r = m2; } printf("%.2lf\n", f1(l)); return 0;}