【ETOJ P1057】小e的菜篮子 题解（优先队列）

本文主要是介绍【ETOJ P1057】小e的菜篮子 题解（优先队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

你有一个菜篮子。

接下来会有 $Q$ 次操作，每次操作如下：

• “1 x”，将一个重量为 $x$ 的菜放入到菜篮子中。
• “2”，将菜篮子中重量最大的菜丢掉（如果菜篮子为空，则跳过）。

问 $Q$ 次操作后，菜篮子中剩下的菜的总重量。

输入格式

第一行一个整数 $Q$，表示操作次数。($1\le Q\le 10^5$)

接下来 $Q$ 行，每行一条操作。($1\le x\le 10^9$)

输出格式

一个整数表示答案

输入样例

3
1 5
1 7
2

输出样例

5

---

思路

首先，初始化一个优先队列hmax，并且读取操作次数q。接下来，根据操作次数进行循环，每次循环都会读取一个操作码op。

如果操作码为1，表示需要将一个重量为x的菜放入菜篮子中，此时读取菜的重量x，然后将其添加到优先队列hmax中。

如果操作码为2，表示需要将菜篮子中重量最大的菜丢掉。此时，如果优先队列hmax不为空，就将队列顶部的元素弹出，即丢掉重量最大的菜。

最后，通过一个循环，将优先队列hmax中所有菜的重量相加，得到菜篮子中剩下的菜的总重量ans，并且将其输出。

---

AC代码

#include <algorithm>
#include <iostream>
#include <queue>
#define ll long long
#define AUTHOR "HEX9CF"
using namespace std;priority_queue<int> hmax;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int q;cin >> q;while (q--) {int op;cin >> op;if (op == 1) {int x;cin >> x;hmax.push(x);} else {if (hmax.size()) {hmax.pop();}}}ll ans = 0;while (hmax.size()) {ans += hmax.top();hmax.pop();}cout << ans << endl;return 0;
}

这篇关于【ETOJ P1057】小e的菜篮子 题解（优先队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---