二分 & 三分

zhone-lb / 2025-02-21 / 原文

二分查找

多用于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));