优先队列习题

本文主要是介绍优先队列习题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

    在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

    每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

    因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入描述:

输入包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。 

输出描述:

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。

示例1

输入

复制3 1 2 9

3
1 2 9

输出

复制15

15

备注:

对于30％的数据，保证有n<=1000：
对于50％的数据，保证有n<=5000；
对于全部的数据，保证有n<=10000。

思路：模板题，有观察可知，先加小的再加大的，放入优先队列中。

代码实现中：注意过程的模拟，取出两个数相加，保留其结果再加入原有的队列中进行自动排序

细节：注意数组的空间为n-1（对于每步操作中少了两个加进去一个）

#include <bits/stdc++.h>
using namespace std;
int n;
int a[20010];
int ans=0;
int main(){
	cin>>n;
	priority_queue<int,vector<int>,greater<int>> q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		q.push(a[i]);
	}
	for(int i=0;i<n-1;i++){
		int u=q.top();
		q.pop();
		int v=q.top();
		q.pop();
		q.push(u+v);
		ans+=u+v;
	}
	cout<<ans<<endl;
}

	

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

有一个长度为n的数组，值为 a[i], 牛牛想找到数组中第 k 小的数。比如 1 2 2 3 4  6 中，第 3 小的数就是2.

牛牛觉得这个游戏太简单了，想加一点难度，现在牛牛有 m 个操作，每个操作有两种类型。

1 x  1 代表操作一，给数组中加一个元素 x 。(0 ≤ x ≤ 1e9)

2     2 代表操作二，查询第 k 小的数。如果没有 k 个数就输出−1

输入描述:

第一行有三个整数，n m k,(1≤n,m,k≤2e5)

第二行包含 n 个整数 a[i] ( 0 ≤ a[i] ≤ 1e9)

接下来m行，每行代表一个操作。具体见题目描述

输出描述:

每次查询输出一个第 k 小的数。

示例1

输入

复制5 4 3 1 2 3 4 5 2 1 1 1 3 2

5 4 3
1 2 3 4 5
2
1 1
1 3
2

输出

复制3 2

思路：从小到大排序反而还需要在查找一波，直接弹出来队首一直到剩下k个元素

细节：k可能比剩下的数要大，但反正就是不等于，所以直接判断就行

#include <bits/stdc++.h>
using namespace std;
long long n,m,k,op,x;
long long a[200010];
int main(){
	cin>>n>>m>>k;//n表示有n个数，m表示操作次数，k表示第k小的数 
	priority_queue<int,vector<int>,less<int>>q;
	for(int i=0;i<n;i++){
	cin>>a[i];
	q.push(a[i]);}
	while((int)q.size()>k) q.pop();
	while(m--){
		cin>>op;
		if(op==2) {
			if(q.size()!=k) cout<<-1<<endl;
			else cout<<q.top()<<endl;
			
		}
		else{
			cin>>x;
			q.push(x);
			if((int)q.size()>k)q.pop();
		}	
		}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans=0;
long long steps=0;
const long long N=150000;
struct data{
	long long time;
	long long step;
	data(long long a=0,long long b=0):
		time(a),step(b){}
};
struct cmp{
	bool operator()(data a,data b){
		if(a.time==b.time) return a.step<b.step;
		return a.time<b.time;
	}
};
int main(){
	priority_queue<data,vector<data>,cmp> q;
	cin>>n;
	data t[n];
 for(int i=0;i<n;i++) {
 	cin>>t[i].time>>t[i].step;
 	q.push(data(t[i].time,t[i].step));
 }
 for(int i=0;i<n;i++){
 	while(!q.empty()){
	 	data d=q.top();
	    steps+=d.time;
	 	if(d.step<=steps) {
		ans++;
	 	q.pop();}
	 	else{
		 	q.pop();
		 }
	 }
 }
	cout<<ans<<endl;
	
} 

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全 毁坏。

现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。

如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

输入描述:

第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。

输出描述:

输出一个整数S，表示最多可以抢修S个建筑.

N < 150,000;  T1 < T2 < maxlongint

示例1

输入

复制4 100 200 200 1300 1000 1250 2000 3200

4
100 200
200 1300
1000 1250
2000 3200

输出

复制3

3

思路：搞不明白为什么要先从最着急的开始排而不是时间最小的开始排。

反正先排了一次，最着急的在前面

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> s;
int n;
struct Node{
	int t,d;
}ti[150010];
bool cmp(Node a,Node b){
	return a.d<b.d;
}
int main(){
	int sum=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>ti[i].t>>ti[i].d;
	sort(ti+1,ti+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum+=ti[i].t; 
		s.push(ti[i].t);
		while(sum>ti[i].d){
			sum-=s.top();
			s.pop();
		}
	}
	cout<<s.size()<<endl;
	return 0; 
}

这篇关于优先队列习题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！