高校工会网站建设,wordpress 导航固定,华大基因 网站建设,电商创业需要多少资金✨题目链接#xff1a; 天使果冻 ✨题目描述 Angelic Jelly 有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。 天使非常喜欢吃果冻#xff0c;但她想把最好吃的果冻留到最后收藏。天使想知道前 x 个果冻中#xff0c;美味度第二大的果冻有多少美味度#xff1f; 一共有 q…
✨题目链接 天使果冻 ✨题目描述
Angelic Jelly 有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。 天使非常喜欢吃果冻但她想把最好吃的果冻留到最后收藏。天使想知道前 x 个果冻中美味度第二大的果冻有多少美味度 一共有 q次询问。 注如果最大的数有两个以上默认第二大的等于最大的。例如 [2,3,4,2,4]这个序列第二大的数是4。 ✨输入描述: 第一行一个正整数 n 。 第二行 n 个正整数 ai用空格隔开。 第三行一个正整数 q 。 接下来的 q 行每行一个正整数 x 代表一次询问。 数据范围1≤q≤1e51≤ai≤1e92≤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;vectorint v(n 1);priority_queueint 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;
} ※ 如果文章对你有帮助的话可以点赞收藏谢谢支持
