二分查找

多用于dp优化

源码

//自己写的时候推荐把边界放宽一点
while(r-l>1) {	//最后一个小于k的位置
	int mid=l+r>>1;
	if(a[mid]<x) l=mid;
	else r=mid-1;
}
if(a[r]<x) l=r;

STL库函数

注意以下返回的都是指针

#include<algorithm>
upper_bound(a+1,a+n+1,k)		//第一个大于k的位置
lower_bound(a+1,a+n+1,k)		//第一个大于等于k的位置
bool cmp(int x,int k) {			//自定义规则，注意k是给定参数，不是a[]的元素
	return val[x]<=val[k];
}
lower_bound(a+1,a+n+1,k,cmp)		//第一个不符合cmp的位置
upper_bound(a+1,a+n+1,k,cmp)		//最后一个符合cmp的位置

细节处理

给定不降序列\(\{a_n\}\)，数 \(x\) ,求：

1、小于\(x\)的最大值的位置

边界：\(a[l]<x,a[r]<x,r-l=1\)

二分答案

01分数规划

\(\color{red} {^*}\)核心：抽象出 \({\sum s_i}-ans*{\sum p_i}=0\) ，求最大值则判大于0，求最小值则判小于0

模型

有一些二元组 \((s_i,p_i)\)，从中选取一些二元组，使得\(\frac {\sum s_i}{\sum p_i}\)最大。

设 \(\frac {\sum s_i}{\sum p_i}=ans\)，则 \({\sum s_i}-ans*{\sum p_i}=0\) （核心公式）

即 \(\sum{(s_i-ans*p_i)}=0\)

二分 \(ans\) ，将每个二元组赋权值 \(s_i-ans*p_i\) ，贪心找大于0的数。

若存在最优答案>=0，则当前二分值偏小。否则，说明偏大。

p.s. 也有除数为连续区间长的，即 \(p_i=1\) 且不能跳选，赋值 \(s_i-ans\) 求最大子段和即可。

例题

例1：[P3199] 输出平均值最小的环的平均值

n<=3000,m<=10000

例2：有带权图G, 对于图中每条边\(e[i]\), 都有\(benifit[i]\)(收入)和\(cost[i]\)(花费), 我们要求的是一棵生成树T, 它使得 \(∑(cost[i]) / ∑(benifit[i]), i∈T\) 最小.

P3778 [APIO2017] 商旅

先是分数规划，\(\sum w-ans*t\le0\)

该环可以分成根据包里的物品分成若干段，分段考虑，对于段\(i\to j\)，最大权为\(max_{l=1}^k\{s[j][l]-b[i][l]\}-ans*dis[i][j]\)，预处理后，floyd跑最大环即可

p.s. 想要分层图+SPFA的我像个sb

p.s.s. 这题卡精度，有个答案是\(0.999999998\)，要开\(long\ double,eps=10^{-9}\)才能过

整体二分

三分

细节说明

边界

对于整数下标的三分，可能出现\(m_1=l\text{或}\ m_2=r\)的情况，此时$\ [l,r]\ $较小，可以直接枚举。

	int l=1,r=MAXN;
	while(true) {
		int m1=l+(r-l)/3,m2=r-(r-l)/3;
		if(l==m1||r==m2) break;
		if(Check(m1)<Check(m2)) r=m2;
		else l=m1;
     	}	
  	ans=Check(l);
	for(int i=l+1;i<=r;i++)	ans=min(ans,Check(i));

不适用情况

答案符合单峰函数，但是变化幅度过小（尤其是整数三分）,使得Check(m1)==Check(m2)，不知道转移方向 （整数三分事真多）

解决方法

1、一定条件下转换成二分来用

2、去重（不是枚举去重，是找贡献点，因为变化幅度小的贡献点很少）

例：[P1314] 上述两种都适用

[P6619] 构成单峰的是两段单调的曲线，考虑它们分别产生贡献的两段，分别二分找答案即可

P3745 [六省联考 2017] 期末考试

E. 延误列车

首先放到\(x-t\)图上，即为若干个抛物线

题意即为求一个时刻\(t_0\)，使得所有抛物线以与\(t=t_0\)的直线的交点为顶点时，都会走到\(x=d\)处

即求一个\(d\)使得上凸函数\(f_i(t)\ge d\)，下凸函数\(f_j(t)\le d\)

即为\(\min(f_i(t))\ge d\)且\(\max(f_j(t))\le d\)

两式相减得\(\min(f_i(t))-\max(f_j(t))\ge 0\)

令\(g(t)=\min(f_i(t))-\max(f_j(t))\)可以证明上凸，用三分求出