用对顶堆做的注意点
查看原帖
用对顶堆做的注意点
423054
人生如旅楼主2025/2/1 12:44

插入大量数字之后先把大根堆的大小调整为i,再调整堆的有序,最后再调整大根堆的数字保持为i,如果在插入大量数字之后先调整有序再调整大根堆的大小就会超时

#include<iostream>
#include<queue>
using namespace std;
#define MAX 200010
typedef long long ll;
int n,m,s;
int add[MAX];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>add[i];
	}
	priority_queue<int,vector<int> ,greater<int> > down;//小根堆
	priority_queue<int> up;//大根堆 
	int j=0;
	for(int i=1; i<=m; i++) {
		int query;
		cin>>query;
		while(j<query) {//插入到优先队列,
			if(up.size()==0||add[i]<=up.top())up.push(add[++j]);
			else down.push(add[++j]);
		}
		while(up.size()>i) {  //先调整顺序就会tle,先把一个堆变小 
			down.push(up.top());
			up.pop();
		}
		while(up.size()<i) { 
			up.push(down.top());
			down.pop();
		}
		while(up.size()!=0&&down.size()!=0&&up.top()>down.top()) {
			down.push(up.top());
			up.pop();
		}
		while(up.size()>i) { 
			down.push(up.top());
			up.pop();
		}
		while(up.size()<i) { 
			up.push(down.top());
			down.pop();
		}
		cout<<up.top()<<endl;
	}
}
2025/2/1 12:44
加载中...