企业官网建设流程全解析

做网站必须要数据库么,网站服务器 免费,网站关键词怎么优化到首页,产品推广方案模板csp信奥赛C标准模板库STL案例应用20 priority_queue实践 题目描述 有两个长度为 NNN 的单调不降序列 A,BA,BA,B#xff0c;在 A,BA,BA,B 中各取一个数相加可以得到 N2N^2N2 个和#xff0c;求这 N2N^2N2 个和中最小的 NNN 个。 输入格式 第一行一个正整数 NNN#xff1b…csp信奥赛C标准模板库STL案例应用20priority_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输入 13 2 6 6 1 4 8输出 13 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≤1051 ≤ 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]能产生的最小和使用最小堆维护当前所有可能的候选和每次取出最小和并补充新的候选算法正确性证明初始时将每个A[i]与B[1]的和加入堆中这N个和是所有A[i]能产生的最小和每次取出堆顶当前最小和A[i]B[j]输出后将A[i]B[j1]加入堆中因为这是同一个A[i]的次小可能和这样保证堆中始终维护着每个A[i]的当前最小候选和经过N次取出操作即可得到全局最小的N个和时间复杂度O(N log N)因为进行了N次堆插入和N次堆删除每次堆操作O(log N)空间复杂度O(N)堆中最多存储N个元素代码实现#includebits/stdc.husingnamespacestd;constintN1e510;// 最大数据范围intn,a[N],b[N];// 存储两个输入序列// 定义堆中存储的节点结构structnode{intsum;// 当前和a[i] b[j]inti;// 在序列A中的索引intj;// 在序列B中的索引// 重载小于运算符使优先队列成为最小堆// 注意返回sum other.sum这样堆顶就是最小sumbooloperator(constnodeother)const{returnsumother.sum;}};priority_queuenodeq;// 最小堆用于维护候选和intmain(){// 读入数据cinn;for(inti1;in;i)cina[i];for(inti1;in;i)cinb[i];// 初始化堆将每个A[i]与B[1]的和作为初始候选// 对于每个固定的A[i]这是它能产生的最小和for(inti1;in;i){q.push({a[i]b[1],i,1});}vectorintv;// 存储结果最小的N个和// 进行N次提取每次得到当前最小的和for(intk1;kn;k){node nowq.top();// 获取当前最小和q.pop();// 从堆中移除v.push_back(now.sum);// 记录结果// 如果当前组合中的B还有下一个元素// 则将同一个A[i]与下一个B[j1]的和加入堆中// 因为对于固定的A[i]B[j1]是下一个最小的可能和if(now.j1n){q.push({a[now.i]b[now.j1],now.i,now.j1});}}// 输出结果for(inti0;in;i){coutv[i] ;}return0;}功能分析1. 数据结构设计结构体node封装一个组合和及其来源索引sumA[i] B[j]的和i在A序列中的位置j在B序列中的位置最小堆priority_queue维护当前所有候选的最小和vector v存储最终结果最小的N个和2. 核心算法流程初始化阶段读取两个长度为N的单调不下降序列对于每个A[i]计算A[i]B[1]这是该A[i]能产生的最小和将这N个初始候选加入最小堆迭代提取阶段循环N次从堆顶取出当前最小和设为A[i]B[j]将该和加入结果集如果B[j]不是最后一个元素计算A[i]B[j1]并加入堆中这是关键步骤保证了每个A[i]的候选和按B的索引递增被考虑输出阶段将结果向量中的N个和按顺序输出3. 算法特点优势高效仅需O(N log N)时间远优于暴力O(N²)节省空间堆中最多存储N个元素空间复杂度O(N)利用有序性充分利用了两个序列的单调不下降特性关键保证堆中始终包含每个A[i]的当前最小候选和每次取出的都是全局最小候选和通过补充A[i]B[j1]确保不会遗漏任何可能的更小和4. 示例验证以样例为例N3 A: 2 6 6 B: 1 4 8执行过程初始堆213, 617, 617 → 堆[3(2,1), 7(6,1), 7(6,1)]取出3补充246 → 堆[6(2,2), 7(6,1), 7(6,1)]取出6补充2810 → 堆[7(6,1), 7(6,1), 10(2,3)]取出7补充6410 → 堆[7(6,1), 10(2,3), 10(6,2)]已取出3个和3,6,7 → 结束输出3 6 7与样例一致。5. 边界情况处理N1时直接输出A[1]B[1]序列元素值较大时使用int足够最大2×109 ^99在int范围内序列完全相同时算法依然正确工作完整系列资料请查看专栏《csp信奥赛C标准模板库STL》https://blog.csdn.net/weixin_66461496/category_13108077.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}