csp信奥赛C++标准模板库STL案例应用20

csp信奥赛C++标准模板库STL案例应用20

priority_queue实践

题目描述

有两个长度为N NN的单调不降序列A , B A,BA,B，在A , B A,BA,B中各取一个数相加可以得到N 2 N^2N2个和，求这N 2 N^2N2个和中最小的N NN个。

输入格式

第一行一个正整数N NN；

第二行N NN个整数A 1 … N A_{1\dots N}A1…N​。

第三行N NN个整数B 1 … N B_{1\dots N}B1…N​。

输出格式

一行N NN个整数，从小到大表示这N NN个最小的和。

输入输出样例 1

输入 1

3 2 6 6 1 4 8

输出 1

3 6 7

说明/提示

对于50 % 50\%50%的数据，N ≤ 10 3 N \le 10^3N≤103。

对于100 % 100\%100%的数据，1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤105，1 ≤ a i , b i ≤ 10 9 1 \le a_i,b_i \le 10^91≤ai​,bi​≤109。

思路分析

该问题需要从两个单调不下降序列的所有两两组合和中找出最小的N个和。直接计算所有N²个组合会超时，因此需要使用更高效的算法。

核心思路：

• 利用两个序列的有序性，采用多路归并的思想
• 对于每个A[i]，它与B[1]的和是该A[i]能产生的最小和
• 使用最小堆维护当前所有可能的候选和，每次取出最小和并补充新的候选

算法正确性证明：

1. 初始时，将每个A[i]与B[1]的和加入堆中，这N个和是所有A[i]能产生的最小和
2. 每次取出堆顶（当前最小和）A[i]+B[j]，输出后
3. 将A[i]+B[j+1]加入堆中，因为这是同一个A[i]的次小可能和
4. 这样保证堆中始终维护着每个A[i]的当前最小候选和
5. 经过N次取出操作，即可得到全局最小的N个和

时间复杂度：O(N log N)，因为进行了N次堆插入和N次堆删除，每次堆操作O(log N)
空间复杂度：O(N)，堆中最多存储N个元素

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;// 最大数据范围intn,a[N],b[N];// 存储两个输入序列// 定义堆中存储的节点结构structnode{intsum;// 当前和：a[i] + b[j]inti;// 在序列A中的索引intj;// 在序列B中的索引// 重载小于运算符，使优先队列成为最小堆// 注意：返回sum > other.sum，这样堆顶就是最小sumbooloperator<(constnode&other)const{returnsum>other.sum;}};priority_queue<node>q;// 最小堆，用于维护候选和intmain(){// 读入数据cin>>n;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++)cin>>b[i];// 初始化堆：将每个A[i]与B[1]的和作为初始候选// 对于每个固定的A[i]，这是它能产生的最小和for(inti=1;i<=n;i++){q.push({a[i]+b[1],i,1});}vector<int>v;// 存储结果：最小的N个和// 进行N次提取，每次得到当前最小的和for(intk=1;k<=n;k++){node now=q.top();// 获取当前最小和q.pop();// 从堆中移除v.push_back(now.sum);// 记录结果// 如果当前组合中的B还有下一个元素// 则将同一个A[i]与下一个B[j+1]的和加入堆中// 因为对于固定的A[i]，B[j+1]是下一个最小的可能和if(now.j+1<=n){q.push({a[now.i]+b[now.j+1],now.i,now.j+1});}}// 输出结果for(inti=0;i<n;i++){cout<<v[i]<<" ";}return0;}

功能分析

1. 数据结构设计

• 结构体node：封装一个组合和及其来源索引
  • sum：A[i] + B[j]的和
  • i：在A序列中的位置
  • j：在B序列中的位置
• 最小堆priority_queue：维护当前所有候选的最小和
• vector v：存储最终结果（最小的N个和）

2. 核心算法流程

初始化阶段：

• 读取两个长度为N的单调不下降序列
• 对于每个A[i]，计算A[i]+B[1]（这是该A[i]能产生的最小和）
• 将这N个初始候选加入最小堆

迭代提取阶段（循环N次）：

1. 从堆顶取出当前最小和（设为A[i]+B[j]）
2. 将该和加入结果集
3. 如果B[j]不是最后一个元素，计算A[i]+B[j+1]并加入堆中
   • 这是关键步骤：保证了每个A[i]的候选和按B的索引递增被考虑

输出阶段：

• 将结果向量中的N个和按顺序输出

3. 算法特点

优势：

• 高效：仅需O(N log N)时间，远优于暴力O(N²)
• 节省空间：堆中最多存储N个元素，空间复杂度O(N)
• 利用有序性：充分利用了两个序列的单调不下降特性

关键保证：

• 堆中始终包含每个A[i]的当前最小候选和
• 每次取出的都是全局最小候选和
• 通过补充A[i]+B[j+1]，确保不会遗漏任何可能的更小和

4. 示例验证

以样例为例：

N=3 A: 2 6 6 B: 1 4 8

执行过程：

1. 初始堆：2+1=3, 6+1=7, 6+1=7 → 堆：[3(2,1), 7(6,1), 7(6,1)]
2. 取出3，补充2+4=6 → 堆：[6(2,2), 7(6,1), 7(6,1)]
3. 取出6，补充2+8=10 → 堆：[7(6,1), 7(6,1), 10(2,3)]
4. 取出7，补充6+4=10 → 堆：[7(6,1), 10(2,3), 10(6,2)]
5. 已取出3个和：3,6,7 → 结束

输出：3 6 7，与样例一致。

5. 边界情况处理

• N=1时：直接输出A[1]+B[1]
• 序列元素值较大时：使用int足够（最大2×109 ^99，在int范围内）
• 序列完全相同时：算法依然正确工作

完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》
https://blog.csdn.net/weixin_66461496/category_13108077.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}