AcWing 838. 同时用down和upAC
原题链接
简单
作者:
天长地鸠
,
2024-02-24 11:14:30
,
所有人可见
,
阅读 24
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], size_h;
int n, m;
void h_down(int u) {
int t = u;
if (u * 2 <= size_h && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size_h && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (t == u) return;
swap(h[t], h[u]);
h_down(t);
}
void h_up(int u) {
while (u / 2 && h[u] < h[u / 2]) {
swap(h[u], h[u / 2]);
u /= 2;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
h[++size_h] = x;
h_up(size_h);
}
for (int i = 0; i < m; i++)
{
cout << h[1] << ' ';
h[1] = h[size_h--];
h_down(1);
}
return 0;
}