PAT 1143

题目 ： Lowest Common Ancestor

分值 ： 30
难度 ： 水题
思路 ： 一个 map标记元素是否出现过,最近的节点大小一定介于他们两者之间,并且肯定先于他们插入
       所以按照插入的顺序遍历,找到第一个节点大小介于两者之间的节点就是他们的最近祖先。
坑点 ：

具体代码如下

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
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map <int , bool> db;
vector<int> vec ;
int main() {
    int M , N ,temp,c1,c2;
    cin >> M >> N ;
    for(int i = 0 ; i<  N ; i++)
    {
        cin >> temp;
        db[temp] = true;
        vec.push_back(temp) ;
    }
    for(int i = 0 ; i< M ; i++)
    {
        cin >> c1 >>c2 ;
        if(!db[c1]&& db[c2])
            printf("ERROR: %d is not found.\n",c1) ;
        else if(!db[c2]&& db[c1] )
            printf("ERROR: %d is not found.\n",c2) ;
        else if(!db[c1] && !db[c2])
            printf("ERROR: %d and %d are not found.\n",c1,c2 );
        else {
            for(int ii= 0 ; ii< vec.size();ii++)
            {
                if((c1-vec[ii])*(c2-vec[ii]) < 0)
                {
                    printf("LCA of %d and %d is %d.\n",c1,c2,vec[ii]); break ;
                }
                if( c1 == vec[ii] )
                { printf("%d is an ancestor of %d.\n",c1,c2) ; break ;}
                if( c2 == vec[ii] )
                { printf("%d is an ancestor of %d.\n",c2,c1) ; break ;}
            }
        }
    }
}