优先队列，大根堆，小根堆

106. 动态中位数 - AcWing题库题目大意求奇数个数的数组的中位数思路利用大根堆大到小和小跟堆小到大的性质滑动窗口移动中位数用大根堆存中位数把小于大根堆堆顶的数放大根堆反之放小根堆当大根堆中的数量-小根堆数量2把大根堆的栈顶放小根堆因为中位数在大根堆栈顶的后面比栈顶要小这才是中间的位置#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second void solve(){ int P; cin P; while(P--) { int id, M; cin id M; priority_queueint left; // 大根堆存较小一半 priority_queueint,vectorint,greaterint right; //小根堆较大一半 vectorint ans; for(int i 0; i M; i) { int x; cin x; if(left.empty() || x left.top()) left.push(x); else right.push(x); // 平衡两个堆 if(left.size() right.size() 1) { right.push(left.top()); left.pop(); } else if(right.size() left.size()) { left.push(right.top()); right.pop(); } // 当前总数i1为奇数记录中位数 if((i1) % 2 1) { ans.push_back(left.top()); } } // 输出编号 和 中位数个数 cout id ans.size() endl; // 每行10个输出 for(int i 0; i ans.size(); i) { if(i ! 0 i % 10 0) cout endl; if(i % 10) cout ; cout ans[i]; } cout endl; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; while(_--) solve(); return 0; }506. 相对名次 - 力扣LeetCode题目大意前3个最大的数分别标记为金银铜后面的数按照从大到小排4-n思路用大根堆把每个人的分数和当前的位置对应存起来我们从第一名开始ans[下标]名次#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; void slove(){ priority_queuepairint,intq; int n; cinn; vectorintscore(n); for(int i0;in;i){ cinscore[i]; q.emplace(score[i],i); } int rank1; vectorstringans(n); while(!q.empty()){ int q1q.top().fi; int q2q.top().se; q.pop(); if(rank1)ans[q2]Gold Medal; else if(rank2)ans[q2]Silver Medal; else if(rank3)ans[q2]Bronze Medal; else ans[q2]to_string(rank);//将数字转化为字符串 rank; } for(auto s:ans){ couts ; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; //cin_; while(_--) slove(); return 0; }703. 数据流中的第 K 大元素 - 力扣LeetCode题目大意一组数中第k大的元素思路把这段数组用小根堆存起来删除至小根堆里有k个元素输出栈顶就是第k大#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; //用小跟堆从小到大 priority_queueint,vectorint,greaterintq; int k; //用函数巧妙应对t次新增元素每次进入堆不受前面新增元素的影响 //因为每次新增都会调用函数调用函数时都会有新的调用值 int add(int val){ q.emplace(val); while(q.size()k) q.pop(); return q.top(); } void slove(){ int n; cinkn; vectorintscore(n); for(int i0;in;i){ cinscore[i]; q.emplace(score[i]); } /*for(int i0;in;i){ cinscore[i]; q.emplace(score[i]); if(q.size()k) q.pop(); }*/ int t; cint; while(t--){ int x; cinx; coutadd(x); } } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; //cin_; while(_--) slove(); return 0; }264. 丑数 II - 力扣LeetCode思路unordered_set哈希表去重小根堆排序让当前丑数中的每个元素都乘以2,3,5把不重复的存入根堆里面循环n次得到第n个丑数注意unordered_set去重set去重加排序这个题要存的数太多了占空间用unordered_set好#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; void slove(){ priority_queueint,vectorint,greaterintq; unordered_setintst; q.emplace(1); st.emplace(1); int n; cinn; int ans; for(int i1;in;i){ ansq.top(); q.pop(); int aans*2; int bans*3; int cans*5; if(!st.count(a)){ st.emplace(a); q.emplace(a); } if(!st.count(b)){ st.emplace(b); q.emplace(b); } if(!st.count(c)){ st.emplace(c); q.emplace(c); } } coutansendl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; //cin_; while(_--) slove(); return 0; }