【蓝桥杯国赛】二分法

本文主要是介绍【蓝桥杯国赛】二分法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

“二分法”的代码模板：

（具体参考：查找算法/搜索 | 二分法（python）_python 二分法-CSDN博客）

1. 闭区间：[left, right]

def binary_search1(nums, target):left, right = 0, len(nums) - 1  # 闭区间 [left, right]while left <= right:  # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right+1] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1  # 范围缩小到 [mid+1, right]else:right = mid - 1  # 范围缩小到 [left, mid-1]return left

2. 左闭右开区间：[left, right)

def binary_search2(nums, target):left = 0right = len(nums)  # 左闭右开区间 [left, right)while left < right:  # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1  # 范围缩小到 [mid+1, right)else:right = mid  # 范围缩小到 [left, mid)return left  # 返回 left 还是 right 都行，因为循环结束后 left == right

3. 开区间：(left, right)

def binary_search3(nums: List[int], target: int) -> int:left, right = -1, len(nums)  # 开区间 (left, right)while left + 1 < right:  # 区间不为空mid = (left + right) // 2# 循环不变量：# nums[left] < target# nums[right] >= targetif nums[mid] < target:left = mid  # 范围缩小到 (mid, right)else:right = mid  # 范围缩小到 (left, mid)return right

---

【第十一届pythonB组试题：123】 

1. 题目描述 

2. 难度：⭐⭐⭐

3. 思考分析：（过了90%的数据，剩余的10%超时）

① 利用“二分法”找到每个 l, r 的位置所在的堆。

② 分类讨论：若l,r在同一堆？若l,r不在同一堆？

③ 尽量少用循环，多从“数学”的角度去找公式。

t = int(input())"""
数列的大小为：1+2+3+......+n，
即 数列的个数为 n(1+n)/2
"""#使用 二分法 找到n
def find(left, right, x):left=left; right=rightwhile left<right:mid = (left+right)//2if mid*(1+mid)//2>=x:right = midelse:left = mid+1return leftfor _ in range(t):l, r = map(int, input().split())n_left=find(0, l, l); n_right=find(n_left, r, r)sum_left=n_left*(n_left+1)//2 - lsum_right=n_right*(n_right+1)//2 - rres = 0#中间堆for t in range(n_left+1, n_right):res += t*(t+1)//2#如果 l,r 在同一堆if n_left==n_right:res += (n_right-sum_right)*(n_right-sum_right+1)//2res -= (n_left-sum_left-1)*(n_left-sum_left)//2else:#计算左边res += n_left*(n_left+1)//2res -= (n_left-sum_left-1)*(n_left-sum_left)//2#计算右边res += (n_right-sum_right)*(n_right-sum_right+1)//2print(res)

---

【第十三届C/C++B组试题：卡牌】

1. 题目描述

2. 难度：⭐⭐⭐

3. 要点分析

①将待查找序列设置为“能凑成的套数”，并通过二分找到该值。

②判断mid套是否满足条件。若满足条件每个牌位都能通过补牌 / 不补牌凑到；如果凑不到，则不满足条件。

import datetime
import math
import sysn, m = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))def check(mid):buf = mfor i in range(n):if a[i] >= mid:continueif a[i]+b[i]<mid or mid-a[i]>buf:return 0buf -= (mid-a[i])return 1"""将能凑成的套数设置为有序序列 并通过二分找到该值"""
l, r = 0, 2*n
while l<r:mid = (l+r+1)//2if check(mid):l = midelse:r = mid-1
print(l)

这篇关于【蓝桥杯国赛】二分法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---