題目大意
實作 heap,並輸出 level order
題解
能懶就懶。 C++ 有 heap 實作的函數可以用,可以不用自己寫。
push_heap
的用法是,先把元素放到陣列的最後面,再呼叫此函數即可。
由於 heap 是一個完全二元樹 (Complete Binary Tree),因此該資料結構的 level order 就是由陣列順序直接輸出即可。
AC Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #include <bits/stdc++.h> using namespace std; using ll = long long;
int main() { ios::sync_with_stdio(false); cin.tie(0);
int N, x; vector<int> v; while (cin >> N) { vector<int> mhp, Mhp; while (N--) { cin >> x; mhp.push_back(-x); Mhp.push_back(x); push_heap(mhp.begin(), mhp.end()); push_heap(Mhp.begin(), Mhp.end()); } for (int i:mhp) cout << -i << ' ' ; cout << '\n'; for (int i:Mhp) cout << i << ' ' ; cout << '\n'; } }
|
OJ 連結
連結:https://zerojudge.tw/ShowProblem?problemid=f498