备战蓝桥杯国赛【Day 5】

例题 1：浮点二分——计算 √2

项目	内容
来源	蓝桥云课基础模板
类型	浮点二分
核心	精度控制、区间收缩

题目描述

计算 √2，保留 3 位小数。利用x²在x > 0时的单调递增性。

输入输出

无输入，输出1.414

题解

浮点二分与整数二分的区别：

• 终止条件：right - left >= eps（区间长度）
• eps 选取：保留n位小数，eps = 1e-(n+1)
• 不判相等：浮点数不存在精确相等

left,right=1.0,2.0eps=1e-4# 保留3位小数，精度取1e-4whileright-left>=eps:mid=(left+right)/2.0ifmid*mid>2:right=mid# 中点太大，答案在左半区间else:left=mid# 中点太小或正好，答案在右半区间print(f"{left:.3f}")

推演过程

轮次	区间	mid	mid²	判断
1	[1.0000, 2.0000]	1.5000	2.2500 > 2	right = 1.5000
2	[1.0000, 1.5000]	1.2500	1.5625 < 2	left = 1.2500
3	[1.2500, 1.5000]	1.3750	1.8906 < 2	left = 1.3750
4	[1.3750, 1.5000]	1.4375	2.0664 > 2	right = 1.4375
5	[1.3750, 1.4375]	1.4062	1.9775 < 2	left = 1.4062
6	[1.4062, 1.4375]	1.4219	2.0217 > 2	right = 1.4219
7	[1.4062, 1.4219]	1.4141	1.9996 < 2	left = 1.4141

区间长度1.4219 - 1.4141 = 0.0078 < 0.0001？不对，继续到长度< eps：
最终left ≈ 1.4142，输出1.414

关键细节

坑点	说明
eps太小	循环次数爆炸，1e-6足够，不要1e-10
mid*mid == 2	浮点不能用==，永远走>或<=分支
固定循环次数	for _ in range(100)也可，更稳定

---

例题 2：二分答案——巧克力切割（蓝桥杯 P99）

项目	内容
链接	https://www.lanqiao.cn/problems/99/learning/
类型	二分答案（最大值）
时间限制	1s
空间限制	256MB

题目描述

N块巧克力，H_i × W_i的长方形。切出K块大小相同的正方形，求最大边长。

输入格式

N K H1 W1 H2 W2 ... HN WN

输出格式

一个整数，最大边长。

样例

输入：

2 5 6 5 5 5

输出：

2

题解

单调性分析：边长x越大，每块巧克力切出的块数越少，总块数越少。具有单调性。

check(x)：边长为x时，能否切出至少K块？

• 第i块：(H_i // x) × (W_i // x)块
• 总和>= K则合法

二分策略：求最大值 →check(mid)合法时，left = mid + 1尝试更大

importsysdefsolve():data=sys.stdin.read().strip().split()it=iter(data)N=int(next(it))K=int(next(it))chocolates=[]for_inrange(N):h=int(next(it))w=int(next(it))chocolates.append((h,w))defcheck(x):ifx==0:returnTruecnt=0forh,winchocolates:cnt+=(h//x)*(w//x)returncnt>=K left,right=1,100000ans=1whileleft<=right:mid=(left+right)//2ifcheck(mid):ans=mid left=mid+1else:right=mid-1print(ans)if__name__=='__main__':solve()

推演验证

巧克力：[6x5, 5x5]，K=5 check(3): (6//3)*(5//3)=2*1=2, (5//3)*(5//3)=1*1=1, 总计3 < 5 → False check(2): (6//2)*(5//2)=3*2=6, (5//2)*(5//2)=2*2=4, 总计10 >= 5 → True check(3) False, check(2) True，尝试 check(2) 和 check(3) 之间无整数 答案 = 2 ✓

复杂度分析

指标	复杂度	说明
时间	O(N × log(max(H,W)))	二分约17次，每次遍历N块
空间	O(N)	存储巧克力尺寸

同类对比

题目	区别
例题3（跳石头）	求"最小值最大化"，check用贪心
LeetCode 875	求最小速度，check用累加时间

---

例题 3：二分答案——跳石头（蓝桥杯 P364）

项目	内容
链接	https://www.lanqiao.cn/problems/364/learning/
类型	二分答案（最小值最大化）
标签	贪心 + 二分

题目描述

河道长L，起点到终点间有N块石头。至多移走M块，使得最短跳跃距离尽可能大。求这个最大值。

输入格式

L N M D1 D2 ... DN

D_i：第i块石头与起点的距离。

输出格式

一个整数，最短跳跃距离的最大值。

样例

输入：

25 5 2 2 11 14 17 21

输出：

4

题解

题型识别：“最小值最大化” → 二分答案经典标志。

单调性：如果最短跳跃距离x可行（移走不超过M块），则所有<= x的距离也可行？不对，应该是：如果x可行，则x-1一定可行（更容易满足）。所以可行解具有单调性，二分找最大的可行x。

check(x)：假设最短距离为x，贪心判断需要移走多少块：

• 维护now_idx：当前所在位置
• 遍历石头，如果石头距离 - now_idx < x，移走这块石头
• 否则跳到这里，更新now_idx
• 最后检查终点距离

importsysdefsolve():data=sys.stdin.read().strip().split()it=iter(data)L=int(next(it))N=int(next(it))M=int(next(it))stones=[int(next(it))for_inrange(N)]defcheck(x):now_idx=0# 当前位置cnt=0# 移走石头数foriinrange(N):ifstones[i]-now_idx<x:cnt+=1# 距离太短，必须移走else:now_idx=stones[i]# 可以跳到这里# 最后检查到终点的距离ifL-now_idx<x:ifcnt<M:# 还能移走最后一块returnTruereturnFalsereturncnt<=M left,right=1,L ans=1whileleft<=right:mid=(left+right)//2ifcheck(mid):ans=mid left=mid+1# 尝试更大距离else:right=mid-1print(ans)if__name__=='__main__':solve()

推演验证

L=25, stones=[2,11,14,17,21], M=2 check(4): now=0, cnt=0 i=0: 2-0=2 < 4 → cnt=1, 移走 i=1: 11-0=11 >= 4 → now=11 i=2: 14-11=3 < 4 → cnt=2, 移走 i=3: 17-11=6 >= 4 → now=17 i=4: 21-17=4 >= 4 → now=21 终点: 25-21=4 >= 4 ✓ cnt=2 <= M=2 → True check(5): now=0, cnt=0 i=0: 2 < 5 → cnt=1 i=1: 11-0=11 >= 5 → now=11 i=2: 14-11=3 < 5 → cnt=2 i=3: 17-11=6 >= 5 → now=17 i=4: 21-17=4 < 5 → cnt=3 > M=2 → 但继续 终点: 25-17=8 >= 5 cnt=3 > M=2 → False 答案在4和5之间，最大可行=4 ✓

关键易错点

错误	正确	后果
忘记终点检查	循环后判断L - now_idx < x	最后一段距离可能不足
cnt < M写错	移走最后一块需要cnt < M	边界WA
贪心方向反了	从左到右，能不移就不移	不是最优解

---

例题 4：二分答案——第K大元素（蓝桥杯 P3404）

项目	内容
链接	https://www.lanqiao.cn/problems/3404/learning/
类型	二分答案（第K小）
标签	数学 + 二分

题目描述

n × m乘法表，第i行第j列为i × j。求第k大的元素。

输入格式

n m k

输出格式

一个整数。

样例

输入：

2 4 4

输出：

3

题解

题型识别：“第K小/大” → 二分答案，统计<= x的个数。

check(x)：统计乘法表中有多少个元素<= x

• 第i行：i × j <= x→j <= x // i
• 贡献：min(m, x // i)个

二分策略：找最小的x，使得count(<= x) >= k

importsysdefsolve():n,m,k=map(int,sys.stdin.readline().split())defcheck(x):cnt=0foriinrange(1,n+1):cnt+=min(m,x//i)returncnt left,right=1,n*m ans=0whileleft<=right:mid=(left+right)//2ifcheck(mid)>=k:ans=mid right=mid-1# 尝试更小的else:left=mid+1# 需要更大的数print(ans)if__name__=='__main__':solve()

推演验证

n=2, m=4, k=4 乘法表： 1 2 3 4 2 4 6 8 排序：[1, 2, 2, 3, 4, 4, 6, 8]，第4大=3 check(3): i=1: min(4, 3//1=3) = 3 i=2: min(4, 3//2=1) = 1 cnt = 4 >= 4 → 合法，尝试更小 check(2): i=1: min(4, 2) = 2 i=2: min(4, 1) = 1 cnt = 3 < 4 → 不合法 答案 = 3 ✓

复杂度分析

指标	复杂度	说明
时间	O(n × log(n×m))	n,m <= 5×10^5，约38次二分
空间	O(1)	不存矩阵，直接算

关键优化

优化	效果
i > x时x//i = 0	提前break，减少循环次数
min(m, x//i)	防止j超过列数m

---

例题 5：二分查找——基础模板（LeetCode 704）

项目	内容
链接	https://leetcode.cn/problems/binary-search/
类型	二分查找
难度	🟢 简单

题目描述

给定有序数组nums和目标值target，返回索引，不存在返回-1。

题解

最基础的二分，三种写法对比：

写法1：闭区间[left, right]

classSolution:defsearch(self,nums:List[int],target:int)->int:left,right=0,len(nums)-1whileleft<=right:# 闭区间，left==right有意义mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1# mid不是答案，从mid+1开始else:right=mid-1# mid不是答案，到mid-1结束return-1

写法2：左闭右开[left, right)

classSolution:defsearch(self,nums:List[int],target:int)->int:left,right=0,len(nums)# right是开边界whileleft<right:# left==right时区间为空mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid# mid可能是答案，但不能包含midreturn-1

三种写法对比

写法	初始化	循环条件	left更新	right更新	适用场景
闭区间	0, n-1	left <= right	mid + 1	mid - 1	找特定元素
左闭右开	0, n	left < right	mid + 1	mid	找下界/插入位置
开区间	-1, n	left + 1 < right	mid	mid	浮点二分

---

📊 今日刷题总结

题号	考点	二分类型	难度	核心技巧
1	√2计算	浮点二分	⭐⭐	eps精度控制
2	巧克力切割	二分答案（最大值）	⭐⭐⭐	check统计块数
3	跳石头	二分答案（最小值最大化）	⭐⭐⭐⭐	贪心+终点检查
4	第K大元素	二分答案（第K小）	⭐⭐⭐⭐	数学统计替代遍历
5	二分查找	基础模板	⭐⭐	三种区间写法

---

二分答案万能模板（背下来）

defbinary_search():left,right=最小值,最大值 ans=初始值whileleft<=right:mid=(left+right)//2ifcheck(mid):# mid满足条件ans=mid# 记录答案left=mid+1# 求最大：往右缩# right = mid - 1 # 求最小：往左缩else:right=mid-1# 求最大：往左缩# left = mid + 1 # 求最小：往右缩returnans