AcWing 4860. 置换选择
原题链接
简单
作者:
fei0825
,
2023-05-25 10:07:42
,
所有人可见
,
阅读 32
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
int n, m, x, last;
scanf("%d %d", &n, &m);
priority_queue<int, vector<int>, greater<int>> hp, tmp; //小根堆,hp存当前段,tmp存下一段
bool f = false;
for( int i=0; i<n; i++ ){
scanf("%d", &x);
if( i<m ){ //前m个数无脑加入堆
hp.push(x);
if( i==m-1 ){ //容量满了之后开始输出
last = hp.top();
hp.pop();
printf("%d", last);
f = true; //记录是否是该段第一个输出
}
}
else{
if( x<last ) tmp.push(x); //比上个输出的值小,加入下一段
else hp.push(x); //否则加入当前段
if( hp.empty() ){ //如果当前段为空并且下一段非空,把下一段置成当前段,并清空tmp
swap(hp, tmp);
puts("");
f = false;
}
last = hp.top();
hp.pop();
if( !f ) f = true;
else printf(" ");
printf("%d", last);
}
}
while( hp.size() ){ //输出剩余的数
if( !f ) f = true;
else printf(" ");
printf("%d", hp.top());
hp.pop();
if( hp.empty() ) puts("");
}
f = false;
while( tmp.size() ){ //输出下一段剩余的数
if( !f ) f = true;
else printf(" ");
printf("%d", tmp.top());
tmp.pop();
if( tmp.empty() ) puts("");
}
return 0;
}