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 二分与前缀和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!