听灌多(玄关)
  • 板块灌水区
  • 楼主lzj20110120
  • 当前回复5
  • 已保存回复5
  • 发布时间2025/1/23 10:02
  • 上次更新2025/1/23 12:05:56
查看原帖
听灌多(玄关)
1139975
lzj20110120楼主2025/1/23 10:02

P1801,0分。 代码如下:

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int m, n;
    cin>>m>>n;//输入元素个数m和命令的个数 n
    vector<int> a(m);// 存储要添加的元素
    for(int i=0;i<m;++i) 
	{
        cin>>a[i];//输入元素
    }
    vector<int> u(n);//存执行GET命令的元素添加次数
    for(int i=0;i<n;++i) 
	{
        cin>>u[i];//输入GET命令的元素添加次数
    }
    priority_queue<int> maxHeap;//大根堆,存储较小一半的元素
    priority_queue<int, vector<int>, greater<int> > minHeap;//小根堆,存储较大一半的元素
    int index=0;//遍历输入元素
    int getIndex=0;//遍历GET添加次数的数组
    int i=0;//每执行 GET 命令,i加1,方便输出第i小的数
    while (getIndex<n)//当还有GET命令要处理时
	{
        while(index<u[getIndex])//当添加元素的次数未达到执行GET命令的条件时
		{
            if(maxHeap.empty()/*大根堆空了*/||a[index]<=maxHeap.top())//元素在大根堆的范围
			{
                maxHeap.push(a[index]);//将元素添加到大根堆中
            } 
			else 
			{
                minHeap.push(a[index]);//将元素添加到小根堆中
            }
            index++;//移动到下一个元素
            //调整两个堆的大小,保证大根堆的元素数量比小根堆多 1 或相等
            if(maxHeap.size()>minHeap.size()+1) 
			{
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            } 
			else if(minHeap.size()>maxHeap.size()) 
			{
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
        }
        i++;//同上
        cout<<maxHeap.top()<<endl;//输出大根堆的堆顶元素,即第i小的元素
        getIndex++; //处理下一个GET
    }
    
    return 0;
}

2025/1/23 10:02
加载中...