【題目來源】
https://www.acwing.com/problem/content/840/
【題目描述】
輸入一個長度為 n 的整數數列，從小到大輸出前 m 小的數。
【輸入格式】
第一行包含整數 n 和 m。
第二行包含 n 個整數，表示整數數列。
【輸出格式】
共一行，包含 m 個整數，表示整數數列中前 m 小的數。
【數據范圍】
1≤m≤n≤10^5，
1≤數列中元素≤10^9
【輸入樣例】
5 3
4 5 1 3 2
【輸出樣例】
1 2 3
【算法分析】
● 堆是一棵完全二叉樹。堆可以用一個一維數組（建議下標從 1 開始）進行模擬。
● 堆的數組模擬實現，參見：https://blog.csdn.net/hnjzsyjyj/article/details/146358448
【算法代碼：堆排序】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int h[maxn];
int tot;
int n,m;void down(int u) {int t=u;if(u*2<=tot && h[u*2]<h[t]) t=u*2;if(u*2+1<=tot && 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;tot=n;for(int i=1; i<=n; i++) cin>>h[i];for(int i=n/2; i>=1; i--) down(i);while(m--) {cout<<h[1]<<" ";h[1]=h[tot--];down(1);}return 0;
}/*
in:
5 3
4 5 1 3 2out:
1 2 3
*/
【算法代碼：sort】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int a[maxn];int main() {int n,m;cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i];sort(a+1,a+1+n);//unique(a+1,a+1+n);for(int i=1; i<=m; i++) cout<<a[i]<<" ";return 0;
}/*
in:
5 3
4 5 1 3 2out:
1 2 3
*/
【參考文獻】
https://blog.csdn.net/hnjzsyjyj/article/details/146331059
https://blog.csdn.net/hnjzsyjyj/article/details/146358448
https://www.acwing.com/solution/content/6362/
https://www.acwing.com/solution/content/5541/
?
)
