题目描述

输入一个长度为 n的整数数列，从小到大输出前 m小的数。

输入格式
第一行包含整数 n和 m。
第二行包含 n个整数，表示整数数列。

输出格式
共一行，包含 m个整数，表示整数数列中前 m小的数。

数据范围
1≤m≤n≤105，1≤数列中元素≤109

样例

输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

注意的点 一个是创建堆的时候从下标i = 1 开始要注意 判定条件是
i <= n;

C++ 代码

#include<iostream>
using namespace std;
#include<algorithm>
const int N = 100010;

int px[N];
int mysize ;
void down(int u){
    int t = u;
    if(2 * u <= mysize && px[2*u] < px[t]) t = 2*u;
    if(2 * u + 1 <= mysize && px[2*u+1] < px[t]) t = 2 * u + 1 ;
    if(t != u) {
        swap(px[t] , px[u]);
        down(t);
    }
}
int main(){

    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <=n ; i ++) cin>>px[i]; 
    mysize = n;
    for(int i= n / 2 ; i ; i --) down(i);

    while (m--){
        cout<<px[1];
        px[1] = px[mysize--];
        if(m) cout<<" ";
        down(1);
    }

    return 0;

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla