自动搬运

查看原文

来自洛谷，原作者为

	_neddy **

搬运于2025-08-24 21:36:55，当前版本为作者最后更新于2019-05-02 13:27:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题坑点还是挺多的，前后交了二十多次终于成功。

$STL$大法好！

方法如下：

1. 开两个优先队列，一个大根堆一个小根堆

priority_queue<int, vector<int>, less<int> > a;		
//大根
priority_queue<int, vector<int>, greater<int> > s;
//小根

2. 把输入的前$m$个数塞进大根堆

for (register int i = 1; i <= m; ++i)
{
   int num;
   scanf("%d", &num); //优先队列不能直接输入堆顶
   a.push(num);     //只能用中间变量输入
   //然后再进堆
}

3. 对接下来的$n-m$个数进行筛选，如果比大根堆的根小，就去除根，并把这个数塞进去

for (register int i = m + 1, num; i <= n; ++i)
{
   scanf("%d", &num);
   if (num < a.top()) a.pop(), a.push(num);
}

4. 把大根堆里的数倒进小根堆里

for (register int i = 1; i <= m; ++i)
{
   s.push(a.top()); //大根堆堆顶倒入小根堆
   a.pop();			//大根堆堆顶出堆
} 

5. 输出即可。

完整代码如下：

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

priority_queue<int, vector<int>, less<int> > a;
priority_queue<int, vector<int>, greater<int> > s;
int maxn;

int main()
{
    int n, m, miss = 0;
    scanf("%d %d", &n, &m);
    for (register int i = 1; i <= m; ++i)
    {
        int num;
        scanf("%d", &num);
        a.push(num);
    }
    for (register int i = m + 1, num; i <= n; ++i)
    {
        scanf("%d", &num);
        if (num < a.top())
        {
            a.pop();
            a.push(num);
        }
    }
    for (register int i = 1; i <= m; ++i)
    {
        s.push(a.top());
        a.pop();
    } 
    while(s.size()) printf("%d\n", s.top()), s.pop();
}

求过求顶，让更多的人看到。

拒绝抄袭。