二分
二分的难点在于看出什么时候该用二分.
一般而言二分的题型有三种:
- 数列/函数单调
- 答案单调,二分答案check能不能达成答案
- 最小化最大值/最大化最小值
碰到这三个性质要联想二分能不能做.
例题
CF2037F 有好多怪物在坐标轴上,每个怪物有自己的血量,怪物不会动,你只能选一个点进行攻击,攻击伤害递减(如 1 2 3 2 1 这样递减的攻击,最中心是你的战力),给定战力求击杀k个怪物的最少攻击次数.
发现 攻击次数 是满足单调性的,也就是说这一次满足了下一次攻击也会满足条件,于是考虑二分.
设攻击y次,战力为k,坐标是pos,对每一个点有 $y\max(0,m-|pos-x_i|)\ge h_i$ ,解方程得到 $\lceil\frac hy\rceil+x_i-m\le pos\le m-\lceil\frac hy\rceil+x_i$ 于是转化为区间有n条线段,找到是否存在一个点被k个线段覆盖,直接差分就可以了.(注意如果有一个点不会被消掉就不要进行贡献,不然整段区间是会被切开出现空当导致WA的)
三分
三分用于找一个单峰函数的极值.
用法比较直白,如果一个函数是单峰就可以用,如果有多个峰值那就只好模拟退火或者python启动.
例题
- 三分板子
乍一看可能不知道怎么写这个三分.
只需要记住,三分一次只丢1/3的区间即可.
如此一来两个函数三分的时候丢掉最不可能的情况,如果两个函数值一样就随机丢一个左右区间留下中间区间即可.