蓝桥杯 之 二分

• 二分是十分重要的一个算法，常常用于求解一定范围内，找到满足条件的边界值的情况
• 主要分为浮点数二分和整数二分
• 二分问题，最主要是写出这个check函数，这个check函数最主要就是使用模拟的方法进行求解
  二分查找算法一
  二分算法（二）
  

函数单调

0-1单调

习题

肖恩的n次根

肖恩的n次根

• 这题是一个浮点数二分的问题，我们只用确定区间的左范围和右范围，确定一个精度进行判断，最好是超过题目要求的精度的100

import os
import sys# 请在此输入您的代码
# 浮点数二分法# 判断是否小于等于target
def check(a1,b1,target):ans = 1for i in range(b1):ans *= a1return ans <= targeta,b = map(int,input().split())l,r = 0,1000
while r - l > 1e-9:mid = (l+r)/2if check(mid,b,a):l = mid else:r = midprint(int(r*1000))

分巧克力

分巧克力

• 判断是否存在单调性：当你分到的巧克力的边长越长，那么可以切分的巧克力的数量就越少，所以说是存在这个单调性的
• 那么确定一个二分的范围：最少的边长，肯定是1，最大的边长，那么就可以认为是最长的w,h

import os
import sys# 请在此输入您的代码N,K = map(int,input().split())
cho = []
maxnum = 0
for _ in range(N):h,w = map(int,input().split())maxnum = max(maxnum,h,w)cho.append([h,w])def check(mid):cou = 0for i in range(N):cou += (cho[i][0] // mid )* (cho[i][1] // mid)return cou >= Kl ,r = 1,maxnum
ans = 0 
while l <= r:mid = (l+r) // 2if check(mid):ans = max(ans,mid)l = mid + 1else:r = mid - 1
print(ans)

• 注意上面的题目，有些同学可能判断不了，最后的答案是l还是r,所以我们直接多开一个变量，当满足情况的时候更新答案即可，最后直接输出这个ans
• 当然，在理解的情况，我们当然是输出不满足情况下修改的那个变量，在这个题目当中，就是r

import os
import sys# 请在此输入您的代码N,K = map(int,input().split())
cho = []
maxnum = 0
for _ in range(N):h,w = map(int,input().split())maxnum = max(maxnum,h,w)cho.append([h,w])def check(mid):cou = 0for i in range(N):cou += (cho[i][0] // mid )* (cho[i][1] // mid)return cou >= Kl ,r = 1,maxnum
while l <= r:mid = (l+r) // 2if check(mid):l = mid + 1else:r = mid - 1
print(r)

2.卡牌

2.卡牌

• 确定二分的对象，那就是对于可以组成的牌的套数,对应的范围0到max(a)+max(b),因为尽可能把最大的情况都得包括进去
• check函数的确定，就是检查，我们要求组成mid套牌，能否在每一种牌都可以凑出mid张，如果有一种不满足，提前返回False,当然得考虑这个补充的牌的数量是否超过m

import os
import sys# 请在此输入您的代码n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))def check(mid):needchange = 0for i in range(n):# 模拟判断情况，如果强制情况下都不满足，那直接返回不满足if a[i] + b[i] < mid:return Falseif a[i] < mid:needchange += (mid - a[i] )if needchange > m :return Falsereturn Truel,r = 0,max(a)+max(b)
ans = 0
while l <= r:mid = (l+r) // 2if check(mid):ans = max(ans,mid)l = mid + 1else:r = mid - 1
print(ans)