备战蓝桥杯国赛【Day 13】

📌 写在前面：今天的两道题是蓝桥杯算法赛压轴级别的难题，涉及二分查找+前缀和的高级组合应用，以及差分数组的逆向思维。很多选手在这类题目上直接放弃，但只要掌握核心思想，它们其实有固定的解题套路。本文会用最通俗的语言+最详细的推演+最完整的代码注释，带你彻底攻克这两座大山！

📚 今日刷题清单

一、平摊购买费用

1.1 题目理解

场景：小蓝和小桥买画，每幅画价格cic_ici​。

支付规则：

• 如果ci<kc_i < kci​<k：小蓝付全部cic_ici​，小桥付000
• 如果ci≥kc_i \geq kci​≥k：小蓝付kkk，小桥付ci−kc_i - kci​−k

目标：选mmm幅画，使得L−FL - FL−F最小。

💡LLL= 小蓝付的总金额，FFF= 小桥付的总金额

1.2 核心转化：把支付问题变成"价值"问题

这是解题的第一步，也是最关键的一步！

对于单幅画，计算L−FL - FL−F：

关键发现：

• c<kc < kc<k时：L−F=cL-F = cL−F=c，价格越小越好（选便宜的）
• c≥kc \geq kc≥k时：L−F=2k−cL-F = 2k-cL−F=2k−c，价格越大越好（选贵的）

🎯结论：最优策略一定是——从价格数组的两端各取一些！

• 左边取ttt个最便宜的（c<kc < kc<k的部分）
• 右边取m−tm-tm−t个最贵的（c≥kc \geq kc≥k的部分）

1.3 为什么中间的商品永远不会被选？

画个图你就懂了：

价格排序后： [便宜] ────────────────────── [贵] ↓ 价值=c（越小越好） ↓ 价值=2k-c（越大越好） ←─ 优先选 ──→ ←─ 优先选 ──→ 中间的商品： - 不够便宜（价值 c 不够小） - 不够贵（价值 2k-c 不够小） → 永远不如两端的商品划算！

1.4 二分查找：找最优的ttt（左边取几个）

问题：左边取ttt个，右边取m−tm-tm−t个，ttt是多少时总价值最小？

二分思路：

• ttt太小 → 左边取少了，右边可能取了不够贵的
• ttt太大 → 左边取多了，可能取了接近kkk的（价值大）
• 存在一个最优的ttt

check函数的核心逻辑：

假设当前考虑"左边取midmidmid个"：

• 左边第midmidmid个候选：c[mid]c[mid]c[mid]（价值 =c[mid]c[mid]c[mid]）
• 右边第midmidmid个候选：c[n−m+mid]c[n-m+mid]c[n−m+mid]（价值 =2k−c[n−m+mid]2k - c[n-m+mid]2k−c[n−m+mid]）

比较两者价值：

• 如果c[mid]>2k−c[n−m+mid]c[mid] > 2k - c[n-m+mid]c[mid]>2k−c[n−m+mid]→ 右边更划算，应该少取左边
• 如果c[mid]≤2k−c[n−m+mid]c[mid] \leq 2k - c[n-m+mid]c[mid]≤2k−c[n−m+mid]→ 左边更划算，应该多取左边

1.5 详细推演

输入: n=3, q=1 价格: c = [3, 5, 8] 查询: k=5, m=1 排序后: [3, 5, 8] 前缀和: pre_sum = [3, 8, 16] 二分查找最优 t： l=0, r=1 mid=0: check(5, 1, 0): c[0] = 3 > 5? 否 c[3-1+0] = c[2] = 8 < 5? 否 比较: c[0]=3 vs 2*5-c[2]=10-8=2 3 > 2 → return True → r = 0 循环结束，l=0 计算答案（l=0，全选右边）： 左边取0个，右边取1个（最贵的1个：8） 价值 = 2*k*1 - 8 = 10 - 8 = 2 输出: 2 ✓

1.6 完整代码（超详细注释版）

n,q=map(int,input().split(' '))c=list(map(int,input().split(' ')))# ========== 预处理 ==========c.sort()# 价格从小到大排序# 前缀和数组：pre_sum[i] = c[0] + c[1] + ... + c[i]pre_sum=[0]*(n+1)foriinrange(n):pre_sum[i+1]=pre_sum[i]+c[i]pre_sum.pop(0)# 去掉pre_sum[0]=0，现在pre_sum[i]对应c[i]# ========== check函数：判断"左边取mid个"是否太多了 ==========defcheck(k,m,mid):""" 假设左边取 mid 个商品，判断这个数量是否偏多 返回 True → 左边取多了，应该减少（去右边更划算） 返回 False → 左边取少了，应该增加（继续取左边更划算） """# 情况1：左边第mid个已经 >= k → 不能再选左边了ifc[mid]>k:returnTrue# 左边太亏了，去选右边# 情况2：右边第一个候选还 < k → 右边全是"便宜货"ifc[n-m+mid]<k:returnFalse# 右边也是便宜的，继续选左边# 情况3：核心比较# 左边下一个的价值 = c[mid]（因为 c[mid] < k）# 右边下一个的价值 = 2*k - c[n-m+mid]（因为 c[...] >= k）left_value=c[mid]right_value=2*k-c[n-m+mid]ifleft_value>right_value:returnTrue# 左边更贵，少取左边else:returnFalse# 左边更便宜，多取左边# ========== 处理每个查询 ==========foriinrange(q):k,m=map(int,input().split(' '))# 二分查找最优的左边数量 ll,r=0,mwhilel<r:mid=(l+r)//2ifcheck(k,m,mid):r=mid# 左边取多了，减少else:l=mid+1# 左边取少了，增加# ========== 计算答案 ==========ifl==0:# 一个左边都不选，全选右边 m 个right_sum=pre_sum[n-1]-pre_sum[n-m-1]ans=2*k*m-right_sumprint(ans)else:# 选左边 l 个 + 右边 m-l 个left_value=pre_sum[l-1]right_count=m-l right_sum=pre_sum[n-1]-pre_sum[n-m+l-1]right_value=2*k*right_count-right_sum ans=left_value+right_valueprint(ans)

1.7 关键细节总结

二、商品库存管理

2.1 题目理解

场景：nnn个商品，初始库存都为000。

操作：mmm个操作，每个操作给区间[L,R][L, R][L,R]的所有商品库存+1+1+1。

问题：对于每个操作，如果不执行它，最终有多少商品的库存为000？

2.2 逆向思维：从"不执行"转化为"执行其他所有"

直接思路：对每个操作，模拟执行其他m−1m-1m−1个操作，统计为0的数量。

问题：mmm次模拟，每次O(n)O(n)O(n)，总复杂度O(nm)O(nm)O(nm)，n,m≤3×105n,m \leq 3\times10^5n,m≤3×105会超时！

逆向思维：

不执行操作i后的库存 = 执行所有m个操作的库存 - 操作i的影响 即：final_without_i = final_all - effect_of_i

关键观察：

• 操作iii的影响：给区间[Li,Ri][L_i, R_i][Li​,Ri​]的每个商品+1+1+1
• final_without_i在[Li,Ri][L_i, R_i][Li​,Ri​]区间内的商品 =final_all对应位置−1-1−1
• 其他位置不变

2.3 进一步转化：统计为0的商品

定义：

• final_all[j]= 执行所有操作后，商品jjj的库存
• count0=final_all中值为000的数量（这些商品从未被任何操作覆盖）

对于"不执行操作i"：

• 商品jjj在[Li,Ri][L_i, R_i][Li​,Ri​]外：final_without_i[j] = final_all[j]
  • 如果final_all[j] = 0，则final_without_i[j] = 0✓
• 商品jjj在[Li,Ri][L_i, R_i][Li​,Ri​]内：final_without_i[j] = final_all[j] - 1
  • 如果final_all[j] = 1，则final_without_i[j] = 0✓

结论：

不执行操作i后，库存为0的商品数 = count0（原本就是0的） + count1_in_range_i（操作i区间内，final_all=1的商品数）

2.4 用差分数组计算 final_all

# 差分数组l=[0]*(n+1)foreach operation[L,R]:l[L-1]+=1# 区间左端点+1（0-indexed）l[R]-=1# 区间右端点+1处-1# 前缀和还原final_all=差分数组的前缀和

2.5 详细推演

输入: n=5, m=3 操作1: [1, 2] 操作2: [2, 4] 操作3: [3, 5] 差分数组构建： l = [0, 0, 0, 0, 0, 0] 操作1 [1,2]: l[0]+=1, l[2]-=1 → l=[1,0,-1,0,0,0] 操作2 [2,4]: l[1]+=1, l[4]-=1 → l=[1,1,-1,0,-1,0] 操作3 [3,5]: l[2]+=1, l[5]-=1 → l=[1,1,0,0,-1,-1] 前缀和还原 final_all： index 0: 1 index 1: 1+1 = 2 index 2: 2+0 = 2 index 3: 2+0 = 2 index 4: 2+(-1) = 1 final_all = [1, 2, 2, 2, 1] count0 = final_all.count(0) = 0 处理每个操作： 不执行操作1 [1,2]： 区间 [0,1] final_all 在 [0,1] = [1, 2] count1 = [1, 2].count(1) = 1 答案 = 0 + 1 = 1 ✓ 不执行操作2 [2,4]： 区间 [1,3] final_all 在 [1,3] = [2, 2, 2] count1 = 0 答案 = 0 + 0 = 0 ✓ 不执行操作3 [3,5]： 区间 [2,4] final_all 在 [2,4] = [2, 2, 1] count1 = 1 答案 = 0 + 1 = 1 ✓

2.6 完整代码（超详细注释版）

fromitertoolsimportaccumulateasacc n,m=map(int,input().split())# ========== 差分数组 ==========l=[0]*(n+1)# 多一位，防止R=n时越界total=[]# 存储所有操作，用于后续查询foriinrange(m):L,R=map(int,input().split())total.append([L,R])# 差分：区间[L,R]加1l[L-1]+=1l[R]-=1# ========== 前缀和还原 final_all ==========a=list(acc(l))# a[j] = 商品j的库存（执行所有操作后）# ========== 统计 final_all 中值为0的数量 ==========# 构造时多了一位（l[n]），所以a[n]可能为0# 减去多构造的那一位count0=a.count(0)-1# ========== 处理每个操作 ==========forL,Rintotal:# 操作i的区间 [L, R]（1-indexed）# Python切片：a[L-1:R] 包含商品L到Rcount1=a[L-1:R].count(1)# 答案 = 原本为0的 + 操作i区间内变为0的print(count0+count1)

2.7 更优解法：前缀和优化 count1

如果数据量更大，需要用前缀和优化：

fromitertoolsimportaccumulateasacc n,m=map(int,input().split())l=[0]*(n+1)total=[]foriinrange(m):L,R=map(int,input().split())total.append([L,R])l[L-1]+=1l[R]-=1a=list(acc(l))# 前缀和优化count0=a.count(0)-1# 标记 final_all[j] == 1 的位置is_one=[1ifx==1else0forxina]# prefix_one[i] = is_one[0] + ... + is_one[i-1]prefix_one=[0]*(n+1)foriinrange(n):prefix_one[i+1]=prefix_one[i]+is_one[i]forL,Rintotal:# 区间 [L-1, R-1] 内 is_one 的和count1=prefix_one[R]-prefix_one[L-1]print(count0+count1)

2.8 关键细节总结

三、今日刷题总结

四、结语

今天的两道题都是蓝桥杯国赛级别的压轴难题，但它们都有固定的解题套路：

🌟今日收获：

1. 价值转化：把复杂的支付问题转化为简单的数值比较
2. 两端贪心：排序后从两端取最优，中间永远不考虑
3. 二分最优分割：当选择有单调性时，二分是找最优解的利器
4. 逆向思维：“不执行A” = “执行全部 - 执行A”，避免重复计算
5. 差分+前缀和：区间修改和查询的标准组合拳

记住：遇到"选m个使某值最小/最大"想排序+贪心+二分；遇到"不执行某个操作"想逆向思维+差分！

继续加油，国赛见！💪

如果本文对你有帮助，欢迎点赞 👍 + 收藏 ⭐ + 关注 🔔，你的支持是我持续更新的动力！