二分答案总结

曾经终败给现在 2024-03-30 09:30 187阅读 0赞

二分的三种实现形式：

1.最普通的：

  1. while(l<=r){
  2.         int mid=l+r>>1;
  3.         if(check(mid)){
  4.             ans=mid;
  5.             r=mid-1;
  6.         }else l=mid+1;
  7.     }

2.当二分出来的值必须是某个集合中的值：

把可能出现的值放到数组中，sort一下，再去二分

3.二分实数：

  1. while(r-l>eps){
  2.     double mid=(l+r)/2;
  3.     if(check(mid)){
  4.         r=mid;
  5.     }else l=mid;
  6. }
  7. cout<<r<<'\n';

二分做法的一般步骤：

一、识别出二分做法：

1.最小值最大 or 最大值最小

2.凭空出现一个未知值，枚举一定超时，且满足单调性

3.求最值

二、看二分的值是否满足单调性

1.将二分出来的值趋于正无穷，看是否满足条件

2.将二分出来的值趋于0，看是否满足条件

3.如果一边是0，一边是1，说明满足单调性

三、check（最重要的一步）：

分为两类：

1.在check里面贪心（占绝大多数）：考虑贡献，然后去贪心地满足题干中要求的其它条件
2.在check里面做DP（少数）：按DP做法即可

注意：在check函数里的条件一定要满足单调性，且答案一定是最后一个满足check里面条件的值

发表评论

表情：
评论列表 （有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二分查找总结

      一、概述 1、定义 二分查找是一种广泛使用的搜索算法，主要用于在有序数组（一般是升序，后面的内容也只是针对升序情况）上查找元素 2、主要思想 二分查找算法背后的主

    叁歲伎倆叁歲伎倆/ 0 赞/ 152 阅读

    相关 二分算法总结

    二分查找 简介 二分查找是一种算法，其输入是一个有序的元素列表。 如果要 查找的元素包含在列表中，二分查找返回其位置;否则返回null > 拓展： 酒桌上玩的游

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 234 阅读