news 2026/6/5 0:06:24

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
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;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/5/28 15:55:03

手把手教你识别树莓派5和树莓派4的引脚差异

手把手教你识别树莓派5和树莓派4的引脚差异&#xff1a;别再被“兼容”骗了&#xff01; 你有没有遇到过这种情况&#xff1f; 把一个在树莓派4上跑得好好的HAT模块&#xff0c;插到全新的树莓派5上&#xff0c;结果IC设备找不到、ADC读数乱跳&#xff0c;甚至系统启动都卡住…

作者头像 李华
网站建设 2026/5/31 14:33:06

ClusterGAN深度解析：无监督学习中的聚类与生成双重突破

ClusterGAN深度解析&#xff1a;无监督学习中的聚类与生成双重突破 【免费下载链接】PyTorch-GAN PyTorch implementations of Generative Adversarial Networks. 项目地址: https://gitcode.com/gh_mirrors/py/PyTorch-GAN 在当今人工智能快速发展的时代&#xff0c;无…

作者头像 李华
网站建设 2026/6/1 2:02:03

如何在阿里云上部署TensorFlow训练任务？

如何在阿里云上部署 TensorFlow 训练任务&#xff1f; 今天&#xff0c;一个AI团队正面临这样的挑战&#xff1a;他们需要训练一个图像分类模型用于电商平台的商品识别&#xff0c;但本地GPU资源不足&#xff0c;训练一次耗时超过48小时&#xff0c;且无法支持多任务并行。更麻…

作者头像 李华
网站建设 2026/6/2 13:40:29

TensorFlow模型服务化：gRPC vs HTTP性能对比

TensorFlow模型服务化&#xff1a;gRPC vs HTTP性能对比 在构建高并发、低延迟的AI推理系统时&#xff0c;一个常被低估但至关重要的设计决策浮出水面&#xff1a;通信协议的选择。尤其是在使用 TensorFlow Serving 部署 ResNet、BERT 等复杂模型时&#xff0c;客户端与服务端之…

作者头像 李华
网站建设 2026/6/2 13:42:21

ESP32-CAM在Arduino中的低功耗模式配置核心要点

如何让 ESP32-CAM 真正“省电”&#xff1f;深度睡眠 外设断电实战指南你有没有遇到过这样的尴尬&#xff1a;满怀期待地把一个基于 ESP32-CAM 的监控小项目放进野外&#xff0c;结果电池三天就见底&#xff1f;明明查了资料说 ESP32 支持微安级功耗&#xff0c;怎么实测还是动…

作者头像 李华
网站建设 2026/6/2 13:41:08

如何在TensorFlow中实现注意力机制？

如何在TensorFlow中实现注意力机制&#xff1f; 在现代深度学习系统中&#xff0c;处理序列数据的能力已经成为衡量模型智能水平的关键指标。无论是翻译一段复杂的英文句子、生成连贯的对话回复&#xff0c;还是识别语音中的关键词&#xff0c;模型都需要从输入序列中精准提取相…

作者头像 李华