Java教程

优先队列习题

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

链接:登录—专业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; 
}

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