欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[C++] PAT 1143 Lowest Common Ancestor (30分)

程序员文章站 2022-07-14 14:51:19
...

[C++] PAT 1143 Lowest Common Ancestor (30分)

Sample Input:

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

Sample Output:

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

题解:

根据BST的特性,
对于输入u,v,可以观察a是否是属于[u,v]范围,
若是,则a就是u,v的最小公共祖先,

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

map<int,bool> mp;
int n,m;
vector<int> arr;



int main(){
	cin >> n >>m;
	arr.resize(m);
	for(int i=0;i<m;i++){
		scanf("%d",&arr[i]);
		mp[arr[i]] = true;
	}

	int u,v;
	int a;
	for(int i=0;i<n;i++){
		cin >> u >> v;

		for(int j=0;j<arr.size();j++){
			a = arr[j];
			if(a>v && a<u || a>u && a<v || a==v || a==u) break;
		}
		
		if(mp[u]==false && mp[v]==false){
			printf("ERROR: %d and %d are not found.\n",u,v);
		}
		else if(mp[u]==false || mp[v]==false){
			printf("ERROR: %d is not found.\n",mp[u]==false?u:v);
		}
		else if( a>v && a<u || a>u && a<v){
			printf("LCA of %d and %d is %d.\n",u,v,a);
		}
		else if(a==v || a==u){
			printf("%d is an ancestor of %d.\n",a == u?u:v,a == u? v:u);
		}
		
		
	}

	system("pause");
	return 0;
}
相关标签: C++/PAT