《算法竞赛进阶指南》学习总结 二分与三分

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》学习总结 二分与三分，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3208字，纯文字阅读大概需要5分钟。

内容图文

首先......我是一个很菜很菜的萌新，所以这篇文章写得很详细，有很多我自己的口水话方便我理解，请各位谨慎食用qwq
以前在网上找过很多介绍二分的博客，但都感觉对萌新不太友好，反正我当时连跳石头都没看懂，所以决定自己写一篇！其中有我的想法，也借鉴了书里的很多内容，感谢lyd。

二分答案，顾名思义，就是对我们所需要的答案进行二分，对我们要求的值进行二分。
二分的基础用法是在单调序列或者单调函数当中查找，当答案具有单调性，我们就可以采用二分来计算，当然还有三分，在后面我会详细讲到

整数集合上的二分

在单调递增序列a中查找>=x的数当中最小的一个

while(l<r)
{
int mid=(l+r)>>1;
if(a[mid]>=x) r=mid; //普适模板:if(check()) r=mid;else l=mid+1;，下同。 
else l=mid+1;
}
return a[l];

 

在单调递增序列a中查找<=x的数当中最大的一个

while(l<r)
{
int mid=(l+r+1)>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;    
} 
return a[l];

 

根据以上两种代码形式 可以总结出二分的两种常用形式
1.r=mid,l=mid+1,取中间值的时候,mid=(l+r)>>1;
2.l=mid,r=mid-1,取中间值的时候,mid=(l+r+1)>>1;

注意
1.如果不对mid的取法进行区分，可能会造成出错的情况，在平时的练习当中，希望大家能注意选择，我不再赘述，《进阶指南》里面讲得很详细啦。
2.在二分当中，我们采用的是右移运算而不是除法，是因为右移运算是向下取整的，但除法向0取整。

终止条件：l==r 也就是答案所在的位置啦

实数域上的二分

实数域会方便很多，具体两种方法。

1.给出精度eps 以l+eps<r为条件

while(l+eps<r)
{
//自己写啦！
}

2.暴力循环100次 完全不用担心不够 2^100已经超过了int类型~
for(int i=0;i<100;i++)
{
//自己写.jpg
}

关于二分的知识点大概就是上面这些，但是大家在写代码的时候一定要注意各种边界条件，比如说l和r之间可不可以取等号，又或者mid是+1，-1还是不加不减。
我个人感觉二分当中的坑点很多，反正我经常因为各种乱七八糟的边界条件debug老半天，肯定是编译器的锅！可能我还是比较菜对题目/模板的理解不够深......

下面给出两道练习题
洛谷P1873砍树 题解(附带原OJ链接)

洛谷P2678跳石头(NOIP2015) 题解(附带原OJ链接)

关于三分

三分，顾名思义就是分成三份，它主要用于求单峰函数的极值。
单峰函数，就是一个有极大值或者极小值的函数。
如果有极大值，那么极大值的左边是单调递增，右边单调递减；
如果有极小值，那么极小值的左边是单调递减，右边是单调递增。
其实我脑袋里面已经自动脑补了一个二次函数了......
(但两者不能划等号哦！二次函数是单峰函数，但单峰函数中仅仅是包含了二次函数)

关于单峰函数求极值的分析

以一个有极大值的单峰函数为例(如图所示)
若此函数有纵坐标y1<y2，那么它横坐标的情况就是两种
1.x1和x2都在极大值的左边，并且x1<x2
2.x1在极大值的左边，x2在极大值的右边
通过分析，我们可以发现，x1总在极大值的左边。
若此函数有纵坐标y1>y2，那么它横坐标的情况也是两种。
1.x1和x2都在极大值的右边，并且x1>x2
2.x1在极大值的左边，x2在极大值的右边
通过分析，我们可以发现，x2总在极大值的右边。
根据以上两种操作，我们可以不停进行三分，直到找到极大值，对于有极小值的单峰函数也是同一个道理。

放两张图在这里，大家自行理解吧......

针对有极大值，且有y1<y2的单峰函数

针对有极小值，且有y1>y2的单峰函数。

qwq三分的知识其实比起二分更简单易懂，因为它能解决的题目范围更狭窄，但需要较强的数学思维，在题目中
能够找出单峰函数的思想。 二分只是一个简单的模板，如果运用到具体的问题当中，要先理清楚这道题有没有二分思想，
同时呢，我认为二分当中的核心应该是check()函数。

下面给出一道题

洛谷P1873 传送带(SCOI2010) 题解(附原OJ链接)

二分的题解就到这里了，很感慨。第一次接触二分我还是一个普及组萌新时根本就看不懂跳石头，甚至完全无法理解......

事实证明，成长的道路上荆棘满布，但只要我们勇敢前行，就没有无法克服的艰难险阻！

内容总结

以上是互联网集市为您收集整理的《算法竞赛进阶指南》学习总结 二分与三分全部内容，希望文章能够帮你解决《算法竞赛进阶指南》学习总结 二分与三分所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---