题目描述
输入一个长度为n的整数数列,从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数,表示整数数列。
输出格式
共一行,包含m个整数,表示整数数列中前m小的数。
数据范围
1≤m≤n≤105,
1≤数列中元素≤109
算法1
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], size;
void down(int k)
{
int t = k;
if (k * 2 <= size && h[t] > h[k * 2]) t = k * 2;
if (k * 2 + 1 <= size && h[t] > h[k * 2 + 1]) t = k * 2 + 1;
if (t != k)
{
swap (h[k], h[t]);
down(t);
}
}
int main()
{
int m;
cin >> size >> m;
for (int i = 1; i <= size; i ++) cin >> h[i];
for (int i = size / 2; i; i --) down(i);//建堆;
while (m --)
{
printf("%d ", h[1]);
swap(h[1], h[size]);
size --;
down(1);
}
return 0;
}