三分算法总结

和二分非常类似的一个算法，与二分不同的是

二分是单调的，而三分是一个先增后减或者先减后增

三分可以求出峰值。

注意三分一定是严格单调的，不能有相等的情况。

不过貌似只有求函数最值才用到这个东西，没有二分应用范围那么广。

「一本通 1.2 例 3」曲线

画画图可以发现，满足先减后增

图和雅礼集训里Merchant那道题非常的像，只不过那道题是最大值，可以用二分。

这道题是最小值，用三分雅礼集训

#include<bits/stdc++.h>
#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
", f(l));
	}
	
    return 0;
}

「一本通 1.2 练习 3」灯泡

这道题我主要是推公式推了好久，我一直算错……

首先可以分两种情况

（1）有影子在墙上

（2）没有影子在墙上

没有影子在墙上的时候，通过计算可以得出当光线照在墙角的时候最大。

设人到墙的距离为x

这个时候我们可以得到x的上界h * D / H（相似）

这个时候就可以合并到第一种情况。

第一种情况可以推出影子长度L = x + (D * h - x * H) / (D - x)

不需要化简，只要在程序中可以算出就行了。

这个时候我就猜测，肯定在某个x是最大的。

我就把x等于各种值得情况打印了出来。

果然，有个最值。

那么就三分。

可以看到，三分的应用是在有浮点数的题目中求最值。

#include<bits/stdc++.h>
#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
", f(l));
	}
	
    return 0;
}

bzoj 1857

这是一道省选题。

首先我先观察题目可以发现一个性质。

路径必然是从AB上走一段然后走到CD某个点上然后走到D

首先确定了AB上的一点可以用三分算出最优解

然后我就猜测AB上的点也可以用三分做。

然后就这么做了。

经过长时间的调试。

70分。

然后我就遇到了一些奇怪的问题

sqrt里面要加上EPS，不然相同的点一算为0，浮点数可能弄到负数。10分。

然后我是用参数方程写的，比较复杂，中间有个地方写错了，20分

AC了之后看别人题解发现可以同时维护x坐标的mid和y坐标的mid，且是一一对应的。

我用参数方程就复杂了，思维量和代码量都上升了。

但我懒得改了。

#include<bits/stdc++.h>
#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
", f1(l));
	
    return 0;
}