Skip to main content

二分

参考资料​

二分法​

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

函数 check 的返回值应为 {0,0,⋯ ,0,0,1,1,⋯ ,1,1}\{0,0,\cdots,0,0,1,1,\cdots,1,1\}。

二分后 ll 为第一个 11 的位置；l−1l-1 为最后一个 00 的位置。

三分法​

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

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

例题​

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

洛谷 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]$ 上的最小值。

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

const double eps=1e-9;
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=(r*2+l)/3;
			if(f(m1)<f(m2))r=m2;
			else l=m1;
		}
		cout<<fixed<<setprecision(4)<<f(l)<<'\n';
	}
	return 0;
}

洛谷 P3382 三分​

洛谷 P3382 三分

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

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

const double eps=1e-6;
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=(r*2+l)/3;
		if(f(m1)>f(m2))r=m2;
		else l=m1;
	}
	cout<<fixed<<setprecision(6)<<l<<'\n';
	return 0;
}
Last updated on