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 446 23 26 24 1024 is the root26 and 23 are siblings46 is the parent of 2323 is a child of 10

输出样例：

FTFT 思路：堆排序，字符串处理可以用stringstream AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define N_MAX 1000+2#define INF 0x3f3f3f3fint n, m;vector
                  
                   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;}

转载于:https://www.cnblogs.com/ZefengYao/p/8591882.html

你可能感兴趣的文章