L2-012. 關于堆的判斷
時間限制
400 ms
內存限制
65536 kB
代碼長度限制
8000 B
判題程序
Standard
作者
陳越
將一系列給定數字順序插入一個初始為空的小頂堆H[]。隨后判斷一系列相關命題是否為真。命題分下列幾種：
- “x is the root”：x是根結點；
- “x and y are siblings”：x和y是兄弟結點；
- “x is the parent of y”：x是y的父結點；
- “x is a child of y”：x是y的一個子結點。
輸入格式：
每組測試第1行包含2個正整數N（<= 1000）和M（<= 20），分別是插入元素的個數、以及需要判斷的命題數。下一行給出區間[-10000, 10000]內的N個要被插入一個初始為空的小頂堆的整數。之后M行，每行給出一個命題。題目保證命題中的結點鍵值都是存在的。
輸出格式：
對輸入的每個命題，如果其為真，則在一行中輸出“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; }
?
