求助大佬优先队列大根堆push的复杂度
  • 板块学术版
  • 楼主zhongboxuan123
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/3/1 21:23
  • 上次更新2023/10/23 23:23:42
查看原帖
求助大佬优先队列大根堆push的复杂度
478766
zhongboxuan123楼主2023/3/1 21:23

蒟蒻写了一道题大概push最多用了10000次,然后就炸了,优先队列中的元素会一直递增 题目如下

在一条水平路边,有n个钓鱼湖,从左到右编号为1,2,…,n。佳佳有H个小时的空余时间,他希望利用这个时间钓到更多的鱼。他从1出发,向右走,有选择的在一些湖边停留一定的时间(是5分钟的倍数)钓鱼。最后在某一个湖边结束钓鱼。佳佳从第i个湖到第i+1个湖需要走5×Ti分钟路,还测出在第i个湖停留,第一个5分钟可以钓到Fi条鱼,以后每再钓5分钟,可以钓到的鱼量减少Di,若减少后的鱼量小于0,则减少后的鱼量为0。为了简化问题,佳佳假定没有其他人钓鱼,也没有其他因素影响他钓到期望数量的鱼。请编程求出佳佳最多能钓鱼的数量。

n100n\le100 代码如下

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q; 
int a[110];
int main(){
	int n;
	cin >> n;
	//n表示有几个鱼塘
	int H;
	int x;
	cin >> H;
	H *= 60;//求以5为一个单位的时间
	for(int i = 1;i <= n;i ++){
		cin >> x;
		a[i] = x;
	}
	for(int i = 1;i <= n;i ++){
		cin >> x;
		while(a[i] > 0){
			q.push(a[i]);
			a[i] -= x;
		}	
	}
	long long sum = 0,cnt = 0;
	for(int i = 1;i < n;i ++){
		cin >> x;
		sum += x * 5;
	}
	H -= sum;
	while(H != 0){
		cnt += q.top();
		q.pop();
		H -= 5;
	}
	cout << cnt;
	return 0;
}
2023/3/1 21:23
加载中...