二分模板基础
二分模板细节
1. 二分模板是针对正整数的
如果是负数:
A. 一种简单的方法是转换成正数考虑;
B. 如果一定要用负数做二分,要将(l+r)/2变为(l+r-1)/2,然后(l+r+1)/2变为(l+r)/2。看图
显然红色是错误的指针,按照我们的想法他应该指向-3,而不是-2
2. 二分模板的图是按照 x 轴的样子画的
性质可以一分为二,但是考虑这种图的时候,一定是按照f(1),f(2)…这样画的
推荐题目(二分答案)
https://atcoder.jp/contests/abc161/tasks/abc161_d 正确理解单调性
https://atcoder.jp/contests/abc155/tasks/abc155_d 灵活运用二分
没错,好得很!
确实,真的很好