堆（洛谷P3378）
题目大意
建立支持以下三种操作的堆：
- 输入1 x，将x插入堆中
- 输入2，输出堆的最小值
- 输入3，删除堆的最大值
解题思路
手写堆或者使用STL容器实现。
手写堆
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int heap[N],top=0;
void push(int x){
heap[++top]=x;
for(int i=top;i>1&&heap[i]<heap[i>>1];i>>=1)swap(heap[i],heap[i>>1]);
}
void pop(){
heap[1]=heap[top--];
for(int i=1;(i<<1)<=top;){
int son=i<<1;
if(son<top&&heap[son+1]<heap[son])son++;
if(heap[son]<heap[i]){
swap(heap[son],heap[i]);
i=son;
}else break;
}
}
int main(){
int n;
cin>>n;
while(n--){
int op,x;
cin>>op;
if(op==1){
cin>>x;
push(x);
}else if(op==2)cout<<heap[1]<<endl;
else pop();
}
return 0;
}
STL
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q;
int n;
int main(){
cin>>n;
int op,a;
while(n--){
cin>>op;
switch(op){
case 1:cin>>a;
q.push(a);
break;
case 2:cout<<q.top()<<endl;
break;
case 3:q.pop();
}
}
return 0;
}
合并果子（洛谷P1090）
题目大意
对序列a合并元素至只包含一个元素，合并代价为元素值之和。求最小代价。
解题思路
根据贪心思想，优先合并值小的元素，由于合并后会产生新元素需要更新值，故采用堆即优先队列存储。每次合并最小的两个元素，并将合并值入堆。最后输出总和即可。
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
priority_queue<int,vector<int>,greater<int>>q;
int n;
int main(){
cin>>n;
int a,ans=0;
while(n--){
cin>>a;
q.push(a);
}
while(q.size()>1){
int x=q.top();
q.pop();
int y=q.top();
q.pop();
ans+=(x+y);
q.push(x+y);
}
cout<<ans<<endl;
return 0;
}
中位数（洛谷P1168）
题目大意
给定一个长度为N的非负整数序列A，对于前奇数项求中位数。
解题思路
使用两个堆，一个大根堆，堆顶存最大值，一个小根堆，堆顶存最小值，这样对于中位数而言小于等于中位数的存放在大根堆，大于的存在小根堆。最后保证大根堆元素数等于小根堆元素数即可。mid即更新为中位数。
未知的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
priority_queue<int>q1; //大根堆
priority_queue<int,vector<int>,greater<int>>q2; //小根堆
int n,mid,x;
cin>>n>>mid;
cout<<mid<<endl; //前1项
for(int i=2;i<=n;i++){
cin>>x;
if(x>mid)q2.push(x);
else q1.push(x);
if(i%2){
while(q1.size()!=q2.size()){
if(q1.size()>q2.size()){
q2.push(mid);
mid=q1.top();
q1.pop();
}else{
q1.push(mid);
mid=q2.top();
q2.pop();
}
}
cout<<mid<<endl;
}
}
return 0;
}
最小函数值（洛谷P2085）
题目大意
给定n个函数\(F_i(x)=A_ix^2+B_ix+C_i\)，\(A_i,B_i,C_i\)均给出，均为正整数，求所有函数所有函数值最小的m个，如果最小值有重复需重复输出。
解题思路
由于函数各项系数均为正整数已知函数单调递增，所以对每个函数从1到m取值，计算函数值，使用优先队列存最小值。
未知的代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
priority_queue<int>q;
cin>>n>>m;
for(int i=1;i<=n;i++){
int a,b,c;
cin>>a>>b>>c;
for(int j=1;j<=m;j++){
if(i==1)q.push(a*j*j+b*j+c);
else{
int k=a*j*j+b*j+c;
if(k<q.top()){
q.push(k);
q.pop();
}else break;
}
}
}
vector<int>ret;
while(m--){
ret.push_back(q.top());
q.pop();
}
for(int i=ret.size()-1;i>=0;i--)cout<<ret[i]<<" ";
return 0;
}
蚯蚓（洛谷P2827）
题目大意
解题思路
未知的代码
Cow Coupons G（洛谷P3045）
题目大意
解题思路
未知的代码