蓝桥杯——二分专题

二分分为：实数二分，二分理论题

二分套路题：最小值最大化，最大值最小化

运用二分满足条件：有界，单调。

-1.四种二分模板

//模板 1：左闭右闭 [l, r] —— 最常用 int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return l; /* 作用 找第一个 ≥ target 的位置 特点 无死循环 mid 不用 +1 最终 l = 第一个 ≥ target 最终 r = 最后一个 ＜ target */ // 模板 2：左闭右开 [l, r) —— 找第一个满足条件 int l = 0, r = n; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] < target) { l = mid + 1; } else { r = mid; } } return l; /* 作用 找第一个 ≥ target */ //模板 3：左开右闭 (l, r] —— 找最后一个满足条件 int l = -1, r = n - 1; while (l < r) { int mid = l + (r - l + 1) / 2; // 必须 +1，防死循环 if (nums[mid] <= target) { l = mid; } else { r = mid - 1; } } return l; /* 作用 找最后一个 ≤ target 关键 出现 l = mid ⇒ mid 必须 +1 */ //模板 4：开区间 (l, r) —— 很少用 int l = 0, r = n - 1; while (l + 1 < r) { int mid = l + (r - l) / 2; if (nums[mid] < target) l = mid; else r = mid; } /* */

闭区间写法

1. 找第一个 ≥ target的位置（lower_bound）

if nums[mid] >= target: right = mid - 1 else: left = mid + 1 return left

✅符号：>=

2. 找第一个 > target的位置

if nums[mid] > target: right = mid - 1 else: left = mid + 1 return left

✅符号：>

3. 找最后一个 ≤ target的位置

if nums[mid] <= target: left = mid + 1 else: right = mid - 1 return right

✅符号：<=

4. 找最后一个 < target的位置

if nums[mid] < target: left = mid + 1 else: right = mid - 1 return right

✅符号：<

0.三种二分模版

# lower_bound 返回最小的满足 nums[i] >= target 的 i # 如果数组为空，或者所有数都 < target，则返回 len(nums) # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1] # 闭区间写法 def lower_bound(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 # 闭区间 [left, right] while left <= right: # 区间不为空 # 循环不变量： # nums[left-1] < target # nums[right+1] >= target mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 # 范围缩小到 [mid+1, right] else: right = mid - 1 # 范围缩小到 [left, mid-1] return left # 左闭右开区间写法 def lower_bound2(nums: List[int], target: int) -> int: left = 0 right = len(nums) # 左闭右开区间 [left, right) while left < right: # 区间不为空 # 循环不变量： # nums[left-1] < target # nums[right] >= target mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 # 范围缩小到 [mid+1, right) else: right = mid # 范围缩小到 [left, mid) return left # 或者 right # 开区间写法 def lower_bound3(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] >= target if nums[mid] < target: left = mid # 范围缩小到 (mid, right) else: right = mid # 范围缩小到 (left, mid) return right

1.两个二分模板

找>=x的第一个，mid=（low+high）//2 ，没有就找比他大的下一个数

a=[0,3,5,7,9,11,13] # [0,1,2,3,4,5,6] # low = 0 high =6 mid =3 -----> low=4 high =6 # low = 4 high =6 mid =5 -----> low=4 high =5 # low = 4 high =5 mid =4 -----> low=5 high =5 # break low=high=5 # 找的是靠右的那一个 low=0 high=len(a)-1 def search(low,high,x): # 查找的是后一个 while (low<high): mid =(low+high)//2 # (2+3)//2=2 偏左 if (a[mid]>=x): high=mid else: low=mid+1 print(a[low]) print(a[high]) search(low,high,10) # 查找结果10

找<=x的第一个，mid=（low+high+1）//2 ，没有就找比他小的前一个数

a=[0,3,5,7,9,11,13] # [0,1,2,3,4,5,6] # low = 0 high =6 mid =3 -----> low=3 high =6 # low = 3 high =6 mid =5 -----> low=3 high =4 # low = 3 high =4 mid =4 -----> low=4 high =4 # break low=high=4 # 找的是靠左的那一个 low=0 high=len(a)-1 def search(low,high,x): # 查找的是前一个 while (low<high): mid =(low+high+1)//2 # (2+3+1)//2=3 偏右 if (a[mid]<=x): low=mid else: high=mid-1 print(a[low]) print(a[high]) search(low,high,10) # 查找结果10

二分例题

1.分巧克力（根据题意转为二分，二分找边长N）

import os import sys # 请在此输入您的代码 def check(d): # 检查蛋糕大小为d是否可分 num = 0 for i in range(n): num+=(w[i]//d)*(h[i]//d) if(num>=k):return True else:return False h = [0]*100010 w = [0]*100010 n,k = map(int,input().split()) for i in range(n): # 读入蛋糕大小 h[i],w[i] = map(int,input().split()) L,R = 1,100010 # 结尾更大防止出现边界问题 while L<R: mid=(L+R+1)//2 # 偶数中值为右值 [1,2] -->2 ，没有则取前 if(check(mid)): L=mid else: R=mid-1 print(L) # mid=(L+R)//2 #偶数中值为左值 [1,2] -->1 ,没有则取后 # if(check(mid)): # L=mid+1 # else: # R=mid #print(L-1)

更合理的写法

import sys #设置递归深度 import collections #队列 import itertools # 排列组合 import heapq #小顶堆 import math sys.setrecursionlimit(300000) n,k = map(int,input().split()) save = [] #存放巧克力 Max=1 for i in range(n): temp=list(map(int,input().split())) Max=max(max(temp),Max) # 记录大巧克力边长，之后用于二分 save.append(temp) def check(i): count=0 for a,b in save: count+=(a//i)*(b//i) if count>=k: return True else: return False left=1 right=Max while(left<right): # 找<=x的第一个 mid=(left+right+1)//2 #print(left,mid,right) #print('-'*40) if check(mid): left=mid else: right=mid-1 print(left) #print(right) #print(mid) ''' 2 10 6 5 5 6 测试结果 1 4 6 ---------------------------------------- 1 2 3 ---------------------------------------- 2 3 3 ---------------------------------------- 2 2 3 '''

2.跳石头 （根据题意转为二分，二分找d）

开始在i(i=0)位置，我在跳下一步的时候去判断我这个当前跳跃的距离，如果这个跳跃距离比二分出来的mid小，那这就是一个不合法的石头，应该移走。为什么？我们二分的是最短跳跃距离，已经是最短了，如果跳跃距离比最短更短岂不是显然不合法，是这样的吧。移走之后要怎么做？先把计数器加上1，再考虑向前跳啊。去看移走之后的下一块石头，再次判断跳过去的距离，如果这次的跳跃距离比最短的长，那么这样跳是完全可以的，我们就跳过去，继续判断，如果跳过去的距离不合法就再拿走，这样不断进行这个操作，直到i = n+1，为啥是n+1？河中间有n块石头，显然终点在n+1处。（这里千万要注意不要把n认为是终点，实际上从n还要跳一步才能到终点）。

import sys import collections import itertools import heapq sys.setrecursionlimit(300000) Len,n,m =map(int,input().split()) stone=[] #石头i和到起点的距离 def check(d): num=0 # 可以搬走的数量 pos=0 # 上一块石头位置 for i in range(0,n): # 0 - n-1 作为石头下标,总共n快石头 if (stone[i]-pos<d): # 可以搬走 num+=1 else: # 不能搬走 pos=stone[i] if num<=m: # 搬走的数量小于要求值，可以继续增大 return True else: return False for i in range(n): t=int(input()) stone.append(t) L,R=0,Len while(L<R): mid=(L+R+1)//2 if check(mid): L=mid else: R=mid-1 print(L)

3.青蛙过河（根据题意转为二分，即跳跃距离）

''' 将所有的石头按照区间分类：1步可达的石头，2步可达的石头，，，，显然能通过一步走到，就绝对不通过两步去走 因为石头能被踩的次数是有限的，例如：1，2，3，4，假如最大步长为3，在1的时候，可以一步走到4号石头，但要是 从1走到2，再从2走到4，跟直接从岸上走到2，再从2走到4没有区别，因此，每一次移动，都必须移动到不同标号的区间去 有效的移动只有跨不同区间的移动 步长合法性判断： 对于任意石头i,区间[i,i+x)中的石头可被踩的总数>=2x 证明： 岸，1，2，3，|4，5，6，|7，8，9，岸 按照有效移动理论，在1时，下一步只能走到4去，因此，想要容纳1全部的被踩次数，4号的石头高度应>=1号，而显然， 想要总过河次数>=2x，那么区间[1,3]中石头总高度>=2x，因为出门的第一步必须要有2x次以上，即[1,3]总高度>=2x， 又因4号高度>=1号高度，故区间[2,4]高度之和>=2x，以此类推，可以证明，要想总过河次数>=2x，任一石头编号开始长度为 步长的区间石头总高度之和>=2x 再按照二分法搜索答案，适用二分法的特性：当步长为ans时可满足题目要求，ans+1一定可以满足题目要求 初始解区间[1,n],不断将解区间二分寻找到能够满足题目要求的最小解 '''

import sys import collections import itertools import heapq sys.setrecursionlimit(300000) def check(mid): for i in range(mid,n): if sum[i]-sum[i-mid] <2*x: return False return True n,x = map(int,input().split()) h = list(map(int,input().split())) sum=[0] # 前缀和下标从1开始 temp=0 for i in range(len(h)): # 前缀和 temp=temp+h[i] sum.append(temp) L=0 R=n while(L<R): mid=(L+R)//2 if check(mid): R=mid else: L=mid+1 print(L)

4.实数二分一元三次方程求解（送分）

import sys #设置递归深度 import collections #队列 import itertools # 排列组合 import heapq #小顶堆 import math sys.setrecursionlimit(300000) a,b,c,d = map(float,input().split()) def f(x): return x*x*x*a+x*x*b+x*c+d ans=[] for i in range(-100,100): if f(i)==0: ans.append(i) if f(i)*f(i+1)<0: # 在（i，i+1）内有根 l=i;r=i+1 while(r-l>=0.001): # 保留精度,2位小数,注意循环条件 mid=(l+r)/2 if f(l)*f(mid)<0: r=mid else: l=mid ans.append(l) if f(100)==0: ans.append(100) for i in ans: print("{:.2f}".format(i),end=' ')