企业网站怎么做省钱翠屏区网站建设

企业网站怎么做省钱,翠屏区网站建设,茶楼网站源码,营销相关网站csp信奥赛C标准模板库STL#xff08;10#xff09;#xff1a;priority_queue的使用详解 一、什么是优先队列#xff1f; priority_queue是一种容器适配器#xff0c;它提供了一种可以快速访问“最大”或“最小”元素的队列。它的底层通常由堆#xff08;Heap#xff0…csp信奥赛C标准模板库STL10priority_queue的使用详解一、什么是优先队列priority_queue是一种容器适配器它提供了一种可以快速访问“最大”或“最小”元素的队列。它的底层通常由堆Heap数据结构实现默认是大顶堆因此插入和删除元素的时间复杂度都是O(log n)访问堆顶元素是O(1)。核心思想普通的队列是“先进先出”而优先队列是“优先级高的先出”。这个“优先级”可以是你定义的任何比较规则。二、基本用法头文件与声明#includequeue// 注意不是#include priority_queueusingnamespacestd;// 最常见的声明方式// 1. 默认大顶堆 (降序队列最大的元素在队首)priority_queueintpq1;// 2. 小顶堆 (升序队列最小的元素在队首)priority_queueint,vectorint,greaterintpq2;// 记住这个写法参数解释int队列中存储的数据类型。vectorint用于承载堆的底层容器必须是随机访问容器如vector,deque默认为vector。greaterint是一个仿函数函数对象用于决定比较规则。greater意味着“更大”的优先级反而更低所以成了小顶堆。默认是lessint即“更小”的优先级更低所以是大顶堆。三、核心操作假设我们声明了一个默认的大顶堆priority_queueint pq操作代码功能描述时间复杂度插入元素pq.push(x)将元素x插入优先队列O(log n)访问堆顶pq.top()返回优先级最高的元素大顶堆即最大值O(1)弹出堆顶pq.pop()删除优先级最高的元素不返回值O(log n)队列大小pq.size()返回队列中元素个数O(1)判断空pq.empty()队列为空返回true否则falseO(1)重要注意事项没有pq.front()或pq.back()只有pq.top()用来访问堆顶。pq.pop()只删除不返回。你需要先用pq.top()获取值再pq.pop()删除。清空队列while (!pq.empty()) pq.pop();或直接重新构造pq priority_queueint();。四、在竞赛中的关键应用技巧1. 实现小顶堆想要一个“从小到大”出队的队列例如解决 Dijkstra 最短路算法必须完整声明priority_queueint,vectorint,greaterintminHeap;minHeap.push(3);minHeap.push(1);minHeap.push(4);coutminHeap.top();// 输出 12. 存储自定义类型结构体你需要定义该类型的比较规则。有两种常用方法方法A重载结构体的operator推荐更简洁注意在priority_queue中即使默认是less它也是用operator来比较。但它的逻辑是如果a b为真则认为a的优先级低于bb应该在前面。所以对于大顶堆我们希望大的在前面就应该定义“当a.val b.val时a的优先级低于b”这恰恰就是默认的less行为。因此如果你想用priority_queueNode pq这种简洁形式定义大顶堆需要重载并且逻辑与你想要的“优先级”相反。structNode{intx,y;// 方法A1 希望按 x 值大的优先级高大顶堆booloperator(constNodeother)const{returnxother.x;// 注意这里写 但含义是“当前x小于别的x则优先级低”}// 方法A2 希望按 x 值小的优先级高小顶堆// bool operator (const Node other) const {// return x other.x; // 这里写 实现了反向逻辑// }};priority_queueNodepq;// 将使用方法A1里定义的operator方法B自定义比较类/函数更灵活优先级逻辑更直观。structNode{intx,y;};// 比较类仿函数structcmp{// 希望 Node 按 x 大的优先级高大顶堆booloperator()(constNodea,constNodeb){returna.xb.x;// 如果 a.x b.x则 a 的优先级低于 b}// 如果希望按 x 小的优先级高小顶堆则写 return a.x b.x;};// 声明时传入比较类priority_queueNode,vectorNode,cmppq;// 也可以使用 lambda 表达式 (C11以上注意语法稍复杂)autocomp[](constNodea,constNodeb){returna.xb.x;};priority_queueNode,vectorNode,decltype(comp)pq_lambda(comp);3. 典型解题模式与例题优先队列常用于贪心算法和维护动态极值的场景。模式1合并果子 / Huffman编码问题题目每次选择权值最小的两堆果子合并代价为两堆之和求最小总代价。解法使用小顶堆每次弹出两个最小的计算和再将和压入堆直到只剩一堆。priority_queueint,vectorint,greaterintminHeap;// 将所有果子重量放入minHeapwhile(minHeap.size()1){intaminHeap.top();minHeap.pop();intbminHeap.top();minHeap.pop();intcostab;anscost;minHeap.push(cost);}模式2维护序列的前K大或前K小元素题目求数据流的中位数或输出每次操作后第K大的数。解法使用两个堆对顶堆。例如求中位数大顶堆left存较小的一半数据。小顶堆right存较大的一半数据。保持left.size() right.size()或left.size() right.size() 1则中位数就在堆顶。模式3Dijkstra算法求最短路用小顶堆 (pairint, int 第一维是距离第二维是节点编号) 来替代普通队列可以快速取出当前未确定距离且距离最小的节点将复杂度优化到 O((VE) log V)。usingPIIpairint,int;// (距离 点)priority_queuePII,vectorPII,greaterPIIpq;// 小顶堆按距离排序vectorintdist(n1,INF);dist[start]0;pq.push({0,start});while(!pq.empty()){auto[d,u]pq.top();pq.pop();if(d!dist[u])continue;// 过时的信息跳过for(auto[v,w]:graph[u]){if(dist[v]dist[u]w){dist[v]dist[u]w;pq.push({dist[v],v});}}}模式4带“反悔”的贪心某些问题中我们做出的选择在未来可能需要撤销反悔优先队列可以很好地维护当前的最优选择和备选方案。五、与set/multiset的对比特性priority_queueset/multiset(平衡树)访问最大/最小元素O(1)O(log n)插入元素O(log n)O(log n)删除指定元素不支持(只能删堆顶)O(log n)查找任意元素不支持O(log n)有序遍历不支持支持内存开销较小较大选择策略如果你只需要不断地访问和移除当前最大/最小值用priority_queue。如果你需要频繁查找、删除任意值或需要有序数据用set/multiset。六、总结与要点核心priority_queue是堆用于 O(log n) 插入、O(1) 访问最值、O(log n) 删除最值。声明默认为大顶堆 (less)。小顶堆必须用priority_queueT, vectorT, greaterT。操作只有push(),pop(),top(),empty(),size()。自定义类型必须提供比较规则。重载operator时逻辑要与想要的优先级相反或自定义比较类逻辑更直观。竞赛应用牢记几个模式——合并果子小顶堆贪心、Dijkstra小顶堆优化、对顶堆维护第K大/中位数、反悔贪心。注意事项它不提供迭代器无法遍历无法删除特定元素除非自己实现一个“延迟删除”技术。掌握好priority_queue能让你在解决涉及动态极值、贪心策略的竞赛题目时事半功倍多加练习理解其“优先级”的本质。各种学习资料助力大家一站式学习和提升#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;}