二分

参考资料

• 二分 - OI Wiki
• 整数范围二分的正确写法 - bilibili

二分

check 函数的返回值应为 $\set{0,0,\dots,0,0,1,1,\dots,1,1}$。

二分结束后，$l$ 为第一个 $1$ 的位置，$l-1$ 为最后一个 $0$ 的位置。

整数

int l=x,r=y+1;
while(l<r)
{
	int mid=l+r>>1;
	if(check(mid))r=mid;
	else l=mid+1;
}

实数

double l=x,r=y;
while(r-l>eps)
{
	double mid=(l+r)/2;
	if(check(mid))r=mid;
	else l=mid;
}

三分

单峰函数如果找最大值 f(m1)>f(m2)，找最小值 f(m1)<f(m2)。

double l=x,r=y;
while(r-l>eps)
{
	double m1=(l*2+r)/3,m2=(l+r*2)/3;
	if(f(m1)>f(m2))r=m2;
	else l=m1;
}

例题

洛谷 P2249 【深基13.例1】查找

输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$。

Code (2)

lower bound

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	vector<int> a(n);
	for(auto &x:a)cin>>x;
	while(m--)
	{
		int q;
		cin>>q;
		auto it=lower_bound(a.begin(),a.end(),q);
		cout<<(it!=a.end()&&*it==q?it-a.begin()+1:-1)<<' ';
	}
	return 0;
}

手写二分

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(m--)
	{
		int q;
		cin>>q;
		int l=1,r=n+1;
		while(l<r)
		{
			int mid=l+r>>1;
			if(a[mid]>=q)r=mid;
			else l=mid+1;
		}
		cout<<(l<n&&a[l]==q?l:-1)<<' ';
	}
	return 0;
}

洛谷 P1883 【模板】三分 | 函数

给定 $n$ 个形如 $ax^2+bx+c$ 的二次函数 $f_1(x),f_2(x),\dots,f_n(x)$，设 $F(x)=\max f_i(x)$，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-10;
const int inf=0x3f3f3f3f;
const int N=10005;
double a[N],b[N],c[N];
int n;
double f(double x)
{
	double res=-inf;
	for(int i=1;i<=n;i++)res=max(res,a[i]*x*x+b[i]*x+c[i]);
	return res;
}
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		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 m1=(l*2+r)/3,m2=(l+r*2)/3;
			if(f(m1)<f(m2))r=m2;
			else l=m1;
		}
		cout<<fixed<<setprecision(4)<<f(l)<<'\n';
	}
	return 0;
}

洛谷 P3382 三分

给出一个 $N$ 次函数，保证在范围 $[l, r]$ 内存在一点 $x$，使得 $[l, x]$ 上单调增，$[x, r]$ 上单调减。试求出 $x$ 的值。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-8;
const int N=15;
double a[N];
int n;
double f(double x)
{
	double res=0;
	for(int i=n;i>=0;i--)res=res*x+a[i];
	return res;
}
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	double l,r;
	cin>>n>>l>>r;
	for(int i=n;i>=0;i--)cin>>a[i];
	while(r-l>eps)
	{
		double m1=(l*2+r)/3,m2=(l+r*2)/3;
		if(f(m1)>f(m2))r=m2;
		else l=m1;
	}
	cout<<fixed<<setprecision(6)<<l<<'\n';
	return 0;
}

洛谷 SP4871 BRI - Bridge

有两个城市，中间相隔着一条笔直的河，现在要修路修桥将这两个城市联通，请找出一种方案使总的花费最小。

Solution

参考资料

• Snell's law - Wikipedia

解题思路

根据光学知识，光线通过一段平行介质后与原来平行，所以前后两段路长可以一起计算。

设桥的水平宽度为 $x$，桥的竖直宽度（河的宽度）为 $y$，则桥长为：

$$\sqrt{x^2+y^2}$$

剩余部分的水平宽度为 $a+b$，垂直宽度为 $c-x$，则路长为：

$$\sqrt{(a+b)^2+(c-x)^2}$$

因此总花费为：

$$f(x)=s_2\sqrt{x^2+y^2}+s_1\sqrt{(a+b)^2+(c-x)^2}$$

求导可知 $f(x)$ 是一个单峰函数，可以用 三分法 求 $f(x)$ 的最小值。

$$f'(x)=\frac{s_2x}{\sqrt{x^2+y^2}}+\frac{s_1(x-c)}{\sqrt{(a+b)^2+(c-x)^2}}$$

我开始考虑用 斯涅尔定律 推导公式，但方程两边都带有三角函数，无法直接求解。

参考代码

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-10;
int a,b,c,h,s1,s2;
double f(double x)
{
	return s1*sqrt((a+b)*(a+b)+(c-x)*(c-x))+s2*sqrt(h*h+x*x);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>a>>b>>c>>h>>s1>>s2;
		double l=0,r=c;
		while(r-l>eps)
		{
			double m1=(l*2+r)/3,m2=(l+r*2)/3;
			if(f(m1)<f(m2))r=m2;
			else l=m1;
		}
		cout<<fixed<<setprecision(2)<<f(l)<<'\n';
	}
	return 0;
}