【普及组训练】二分答案

$\huge\text{一、概述}$ 二分是普及/提高组一种常见技巧，用于二分答案/二分查找。 $\huge\text{二、思想}$ 不知你小时候是否玩过这个游戏： $1-1000$ 中给你 $10$ 次机会才一个数，每次对方会告诉你猜大了还是小了。若最终猜对对方就女装。作为一名 $OIer$ ，你自然想看对方女装，所以你千方百计的要猜中。你第一步会猜什么呢？ 你如果猜 $500$ ，那么恭喜你，你的智商很过关！ 为什么呢？因为猜 $500$ 可以排除掉一半的数！ 容易证明猜别的数不会比它效率更高（在你不知道谜底的情况下） 那么你已经掌握了二分的精髓！ 二分模板（整数域） $Code$: ``` int l=可能达到的最小值-1,r=可能达到的最大值+1; while(r-l>1){ int mid=(l+r)/2; if(check(mid)) r=mid(或l=mid); else l=mid(或r=mid); } ``` 实数域的话不再赘述，注意精度，具体细节请看[这里](https://www.baidu.com/link?url=t4-Q_C5-cKSIIl0r3YRs0DPT6yhJsrqAOuAXfaWYWmfTIdTGApYs9MtbmsRXpXaNLrG37_QRGmXn336tgBP9DK&wd=&eqid=fc53d61e0008615c000000065ec4cbde) **思路很简单，细节是魔鬼** 多加历练才是正道。 $\huge\text{三、题目}$ 【红题篇】 - [一元三次方程求解](https://www.luogu.com.cn/problem/P1024) 尝试不要用枚举求解，试试二分。 【橙题篇】 - [进击的奶牛](https://www.luogu.com.cn/problem/P1824) 经典套路：二分答案+贪心判断 - [小车问题](https://www.luogu.com.cn/problem/P1258) 一道不错的题，由余力的同学可以尝试数学解。 【黄题篇】 - [数列分段 II](https://www.luogu.com.cn/problem/P1182) 经典二分例题，值得一做(ps.注意边界，不然你会死的很惨) - [$\text{KC}$喝咖啡](https://www.luogu.com.cn/problem/P1570) 实数域上的二分练手题。注意精度。 - [切绳子](https://www.luogu.com.cn/problem/P1577) 同上题，一样是二分答案+贪心判断。 - [砍树](https://www.luogu.com.cn/problem/P1873) 二分答案+贪心判断 - [木材加工](https://www.luogu.com.cn/problem/P2440) 千万注意不要$RE$，一样是二分答案+贪心判断呦。 - [[USACO06DEC]River Hopscotch S](https://www.luogu.com.cn/problem/P2855) 二分答案+贪心判断 - [[Code+#1]木材](https://www.luogu.com.cn/problem/P4058) 二分答案+贪心判断，同机房神犇竟用 $dp$ ？？？ 【绿题篇】 - [借教室](https://www.luogu.com.cn/problem/P1083) 二分答案+贪心判断，这一题花姐姐的题解写的特别特别棒~~(很啰嗦)~~，大家可以去看看。 - [包裹快递](https://www.luogu.com.cn/problem/P1542) 二分答案+贪心判断，提示关键词：最大值最小$/$最小值最大。 - [[TJOI2007]路标设置](https://www.luogu.com.cn/problem/P3853) 也是一道二分答案+贪心判断，边界值得考虑。 - [[AHOI2018初中组]分组](https://www.luogu.com.cn/problem/P4447) 嘿嘿，抓住一道二分查找的题目了 \se \se 【蓝题篇】 - [聪明的质监员](https://www.luogu.com.cn/problem/P1314) 需要一点数学思维，不过你们一定可以做出来的！ - [山](https://www.luogu.com.cn/problem/P1663) 同上。二分答案+贪心判断，实数域的练习题！ - [[USACO10FEB]Chocolate Eating S](https://www.luogu.com.cn/problem/P2985) 二分答案+贪心判断 ~~怎么这种水题都有这么两次你的题解QwQ~~ - [Chtholly Nota Seniorious](https://www.luogu.com.cn/problem/P3933) 可以看一看第一篇题解~~做一做坐英语填空题~~提高初赛的填代码能力 - [跳房子](https://www.luogu.com.cn/problem/P3957) 经典的二分 $+dp$ ，亿万 $OIer$ 心目中的眼中钉，等着你来宣战！ $\huge\text{四、三分}$ 三分法用来处理单峰函数的极大值，普及组基本不靠，学习一个思想就行了。推荐两道题目： - [【模板】三分法](https://www.luogu.com.cn/problem/P3382) 模板题，可以看看题解学习一下。 - [HDU 3400](https://www.cnblogs.com/cjjsb/p/9179699.html) 可以做一做！/kk $\huge\text{五、后记}$ 笔者文笔不佳，就不写的吧~~~下期预告：排序 $\huge\text{六、鸣谢}$ 感谢【信息学奥赛一本通·学习团】全体成员的支持与鼓励！ 感谢父母给予我的支持！ 感谢我年迈的奶奶与姨婆对我的关心！ 偶然发现以前写的一篇作文，挂出来留念一下：