题目描述

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

输入格式
第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

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

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

样例

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

算法1

(STL)

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int n,m;

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  for(int i=0;i<m;i++)cout<<a[i]<<" ";
  return 0;
}

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m;
int h[N],size;
void down(int u){
    int t=u;
    if(u*2<=size&&h[u*2]<h[t])t=u*2;
    if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1;
    if(u!=t){
        swap(h[u],h[t]);
        down(t);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>h[i];
    size=n;
    for(int i=n/2;i;i--)down(i);
    while(m--){
        cout<<h[1]<<" ";
        h[1]=h[size];
        size--;
        down(1);
    }
}