C/C++教程

(acwing蓝桥杯c++AB组）2.1 二分与前缀和

本文主要是介绍(acwing蓝桥杯c++AB组）2.1 二分与前缀和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分与前缀和

文章目录

  • 二分与前缀和
    • 二分
      • 整数二分核心思想
      • 整数二分步骤总结：
        • 题目链接
      • 实数二分核心思想：
        • 题目链接
      • 三分法思想：

二分

难点：二分的边界问题

整数二分核心思想

  1. 确定一个区间，使得目标值一定在区间中。

  2. 找一个性质满足：（对于百分之95的二分拥有这个性质）

    • 性质具有二段性。
    • 答案是二段性的分界点。

    对于整数二分

image-20211110000409923

image-20211110225717046

整数二分步骤总结：

  1. 找一个区间[L,R]，使得答案一定在该区间中。
  2. 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。
  3. 分析终点M在在该判断条件下是否成立，如果成立，考虑答案在哪个区间。
  4. 如果更新方式写的是R=Mid，则不用做任何处理；如果更新方式写的是L=Mid，则需要再计算Mid时加上1。

题目链接

789. 数的范围 - AcWing题库

下面是本节课总的题单，涉及前缀和等可以先不看跳过。

image-20211111214237772

实数二分核心思想：

实数二分相对于整数比较简单，因为中点是基本可以取到的，没有整数一会加1，一会减去1这么绕。

image-20211112231555764

加一减一无需考虑，可以说是非常简单了（滑稽，第一遍写还是WA了）。只需注意浮点数精度丢失问题，取误差在1e-8即可。

题目链接

790. 数的三次方根 - AcWing题库

三分法思想：

用的不多，这里简单提一下。

对于下图的函数，我们为了找值可以采取对斜率二分（求导即可）。或者，采取下图的三分法，当重复多次后，l与r无线逼近即可。

image-20211112235128598

这篇关于(acwing蓝桥杯c++AB组）2.1 二分与前缀和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航