f679 - 公會成員

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷對於給定的 Q 個玩家編號，他們是否為 N 個公會成員之一。公會成員的編號已排序。

解題思路

本題可以使用二分搜尋法在已排序的公會成員列表中查找每個玩家編號。然而，由於題目中 N 的最大值為 500,000，而 Q 的最大值為 1,000,000,000，如果每次查詢都使用二分搜尋，時間複雜度會達到 O(Q * log N)，可能會超時。

更有效的方法是使用雜湊表 (Hash Table) 來儲存公會成員的編號。雜湊表提供平均 O(1) 的查找時間。首先，將所有公會成員的編號插入雜湊表中。然後，對於每個查詢的玩家編號，檢查它是否存在於雜湊表中。

複雜度分析

• 時間複雜度: O(N + Q)
  • 建立雜湊表需要 O(N) 的時間。
  • 對於每個查詢，雜湊表的查找操作平均需要 O(1) 的時間，因此 Q 個查詢需要 O(Q) 的時間。
• 空間複雜度: O(N)
  • 雜湊表需要儲存 N 個公會成員的編號。

程式碼

#include <iostream>
#include <map>
using namespace std;
map <string,bool> ans;
string a;
int n,m;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	while(n--){
		cin >> a;
		ans[a]=1;
	}
	while(m--){
		cin >> a;
		if(ans[a]){
			cout << "Yes\n";
		}
		else{
			cout << "No\n";
		}
	}
}