Information
- ID
- 333
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 57
- Accepted
- 15
- Uploaded By
当堆大小超过 k 时,pop掉堆顶元素
堆顶元素就是第 k 大的数
#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl "\n"
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long long ll;
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------*/
int n,m;
int h[N],ind,cnt;
void down(int x){
int t=x;
if(2*x<=ind&&h[2*x]<h[t])t=2*x;
if(2*x+1<=ind&&h[2*x+1]<h[t])t=2*x+1;
if(t!=x){
swap(h[x],h[t]);
down(t);
}
}
void up(int x){
int t=x;
if(x/2>=1&&h[x/2]>h[x])t=x/2;
if(t!=x){
swap(h[x],h[t]);
up(t);
}
}
void pop(){
h[1]=h[ind];
ind--;
down(1);
}
void push(int x){
h[++ind]=x;
up(ind);
}
int main(){
ioio
cin>>n>>m;
string op;
int x;
while(n--){
cin>>op;
if(op=="I"){
cin>>x;
push(x);
cnt++;
if(cnt>m)pop();
}
else {
cout<<h[1]<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int t,n,x;
char a;
int main(){
std::ios::sync_with_stdio(false);
priority_queue<int,vector<int>,greater<int> > num;//小顶堆
cin>>t>>n;
while(t--){
cin>>a;
if(a=='I'){
cin>>x;
if(num.size()<n)
num.push(x);
else if(num.top()<x){//当数目大于n是,判断后面的数是否大于队列中最小的数
num.pop();///若小于则没必要加入队列(这样极大的优化了代码)
num.push(x);//若大于,则先出队一个元素,再入队,保持队列中只有n个元素
}
}else{
cout<<num.top()<<endl;
}
}
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.