【算法】Angelic Jelly天使果冻
✨题目链接：
天使果冻
✨题目描述
Angelic Jelly
有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。
天使非常喜欢吃果冻，但她想把最好吃的果冻留到最后收藏。天使想知道前 x 个果冻中，美味度第二大的果冻有多少美味度？一共有 q次询问。
注：如果最大的数有两个以上，默认第二大的等于最大的。例如， [2,3,4,2,4]这个序列，第二大的数是4。
✨输入描述:
第一行一个正整数 n 。
第二行 n 个正整数 ai，用空格隔开。
第三行一个正整数 q 。
接下来的 q 行，每行一个正整数 x ，代表一次询问。
数据范围：1≤q≤1e5，1≤ai≤1e9，2≤x≤n≤1e5
✨输出描述:
输出 q 行，每行一个正整数，代表一次询问，输出前x 个果冻中美味度第二大的值。
✨示例1
📍输入
5
1 2 5 3 5
4
2
3
4
5
📍输出
1
2
3
5
📍说明
前2个数，第二大的是1。
前3个数，第二大的是2。
前4个数，第二大的是3。
前5个数，第二大的是5。
✨解题思路
- 每输入一个果冻的美味度就把ai放到小根堆中
- 从第二个果冻开始：
- 保存当前果冻前最大的ai （小根堆顶）
- 弹出堆顶元素，此时堆顶为前i个果冻中第二大的
- 把满足结果放到 arr[i] 中
- 循环结束把堆顶元素填入最后一个位置arr[n]
- 接收q行的x
- 打印数组arr[x]中的结果
✨代码
#include <iostream>
#include <queue>
#include <vector>
using namespace std;int arr[100000] = { 0 };int main() {int n, q;cin >> n;vector<int> v(n + 1);priority_queue<int> pq;for (int i = 0; i < n; i++) {cin >> v[i];if (i != 0) {pq.push(v[i]);int max = pq.top();pq.pop();arr[i] = pq.top();pq.push(max);} else {pq.push(v[i]);}}pq.pop();arr[n] = pq.top();int x;cin >> q;while (q--) {cin >> x;cout << arr[x - 1] << endl;}return 0;
}
※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持