P3378 【模板】堆

题目描述

给定一个数列，初始为空，请支持下面三种操作：

给定一个整数 x，请将 x 加入到数列中。

输出数列中最小的数。

删除数列中最小的数（如果有多个数最小，只删除 1 个）。

输入格式

第一行是一个整数，表示操作的次数 n。
接下来 n 行，每行表示一次操作。每行首先有一个整数 op 表示操作类型。

若 op = 1，则后面有一个整数x，表示要将 x 加入数列。
若op=2，则表示要求输出数列中的最小数。
若 op = 3，则表示删除数列中的最小数。如果有多个数最小，只删除1 个。

输出格式

对于每个操作 2，输出一行一个整数表示答案。

输入输出样例

输入

输出

2

5

说明/提示

数据规模与约定

对于 30% 的数据，保证 n≤15。
对于 70% 的数据，保证 n≤10^4-。
对于 100% 的数据，保证 1≤n≤10^6,1≤x<2^31，op∈{1,2,3}。

思路1

这道题是堆的模板题目，我们可以用堆来做这题

但是直接用堆来做的话会超时，建议用思路2来做

代码

#include<bits/stdc++.h>

#pragma GCC optimize(100)

using namespace std;

int dui[100001];

int n=0;

void downadjust(int low,int high){

	int i=low,j=i*2;

	while(j<=high){

		if(j+1<=high&&dui[j+1]>dui[j]){

			j=j+1;

		}

		if(dui[j]>dui[i]){

			swap(dui[j],dui[i]);

			i=j;

			j=i*2;

		}else{

			break;

		}

	}

}

void build(){

	for(int i=n/2;i>=1;i--){

		downadjust(i,n);

	}

}

void deletetop(){

	dui[1]=dui[n--];

	downadjust(1,n);

}

void duisort(){

	build();

	for(int i=n;i>=1;i--){

		swap(dui[i],dui[1]);

		downadjust(1,i-1);

	}

}

void upadjust(int low,int high){

	int i=high,j=i/2;

	while(j>=low){

		if(dui[j]<dui[i]){

			swap(dui[j],dui[i]);

			i=j;

			j=i/2;

		}else{

			break;

		}

	}

}

void deleteany(int x){

	dui[x]=dui[--n];

	upadjust(1,x);

	downadjust(x,n);

}

void insert(int i){

	dui[++n]=i;

	upadjust(1,n);

}

int main(){

	ios::sync_with_stdio(false);

	int t;

	cin>>t;

	int a,b;

	int vis=0;

	for(int i=1;i<=t;i++){

		cin>>a;

		vis=0;

		if(a==1){

			cin>>b;

			insert(b);

		}

		else if(a==2){

			duisort();

			vis=1;

			cout<<dui[1]<<endl;

		}

		else{

			duisort();

			deletetop();

		}

	}

	return 0;

}

思路2

这道题我们还可以直接用优先队列，来模拟栈（值小的优先级大，所以要重定义priority_queue）

priority_queue<int,vector<int>,greater<int> >q;

代码

#include<bits/stdc++.h>

using namespace std;

int main(){

	priority_queue<int,vector<int>,greater<int> >q;

	int n;

	cin>>n;

	int a,b;

	for(int i=1;i<=n;i++){

		cin>>a;

		if(a==1){

			cin>>b;

			q.push(b);

		}

		else if(a==2){

			cout<<q.top()<<endl;

		}

		else{

			q.pop();

		}

	}

	return 0;

}

巴特西

P3378 堆（模板）