L2-012. 關(guān)于堆的判斷

時間限制 400 ms 內(nèi)存限制 65536 kB 代碼長度限制 8000 B 判題程序 Standard 作者 陳越

將一系列給定數(shù)字順序插入一個初始為空的小頂堆H[]。隨后判斷一系列相關(guān)命題是否為真。命題分下列幾種：

• “x is the root”：x是根結(jié)點(diǎn)；
• “x and y are siblings”：x和y是兄弟結(jié)點(diǎn)；
• “x is the parent of y”：x是y的父結(jié)點(diǎn)；
• “x is a child of y”：x是y的一個子結(jié)點(diǎn)。

輸入格式：

每組測試第1行包含2個正整數(shù)N（<= 1000）和M（<= 20），分別是插入元素的個數(shù)、以及需要判斷的命題數(shù)。下一行給出區(qū)間[-10000, 10000]內(nèi)的N個要被插入一個初始為空的小頂堆的整數(shù)。之后M行，每行給出一個命題。題目保證命題中的結(jié)點(diǎn)鍵值都是存在的。

輸出格式：

對輸入的每個命題，如果其為真，則在一行中輸出“T”，否則輸出“F”。

輸入樣例： 5 4 46 23 26 24 10 24 is the root 26 and 23 are siblings 46 is the parent of 23 23 is a child of 10 輸出樣例： F T F T

思路：堆排序，字符串處理可以用stringstream
AC代碼： #define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<vector> #include<string> #include<iomanip> #include<map> #include<stack> #include<set> #include<queue> #include<sstream> using namespace std; #define N_MAX 1000+2 #define INF 0x3f3f3f3f int n, m; vector<int>vec; bool cmp(const int &a,const int &b) {return a > b; }int main() {while (cin>>n>>m) {vec.clear();for (int i = 0; i < n; i++) { int a; cin >> a; vec.push_back(a); make_heap(vec.begin(), vec.end(), cmp); }getchar();//吸收空格while (m--) {string s; getline(cin, s);stringstream ss(s);if (s[s.size() - 1] == 't') {int a;ss >> a;if (a == vec[0])puts("T");else puts("F");}else if (s[s.size()-1]=='s') {int a, b; string tmp;ss >> a >> tmp >> b;int pos_a = find(vec.begin(), vec.end(), a) - vec.begin()+1;int pos_b = find(vec.begin(), vec.end(), b) - vec.begin()+1;if (pos_a / 2 == pos_b / 2)puts("T");else puts("F");}else {int a, b; string tmp;ss >> a >> tmp >> tmp;int pos_a = find(vec.begin(), vec.end(), a) - vec.begin() + 1;if (tmp[0] == 't') {ss >> tmp >> tmp >> b;int pos_b = find(vec.begin(), vec.end(), b) - vec.begin() + 1;if (pos_b / 2 == pos_a)puts("T");else puts("F");}else {ss >> tmp >> tmp >> b;int pos_b = find(vec.begin(), vec.end(), b) - vec.begin() + 1;if (pos_a / 2 == pos_b)puts("T");else puts("F");}}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZefengYao/p/8591882.html

總結(jié)

以上是生活随笔為你收集整理的pat 团体天梯赛 L2-012. 关于堆的判断的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。