d573 - CRC騎士團

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取騎士團的編組資訊，並根據輸入的騎士編號，輸出該騎士所屬的組別編號。輸入包含組數、每組的組員數以及組員編號，最後輸入要查詢的騎士編號。

解題思路

這題的核心是建立一個騎士編號到組別編號的映射關係。可以使用一個陣列 crc，其中索引代表騎士編號，數值代表該騎士所屬的組別編號。讀取輸入時，將每個騎士編號對應的組別編號存入 crc 陣列中。讀取完所有組別資訊後，根據輸入的騎士編號，直接從 crc 陣列中讀取對應的組別編號並輸出。

複雜度分析

• 時間複雜度: O(N + X)，其中 N 是組數，X 是騎士總數量。讀取輸入需要 O(N + X) 的時間，查詢騎士編號需要 O(1) 的時間。
• 空間複雜度: O(X)，需要一個大小為 X 的陣列 crc 來儲存騎士編號到組別編號的映射關係。

程式碼

#include <stdio.h>
int main(){
	int crc[100001],n,no,p,x;
	while(scanf("%d",&n)>0){
		while(n--){
			scanf("%d%d",&no,&p);
			while(p--){
				scanf("%d",&x);
				crc[x]=no;
			}
		}
		scanf("%d",&x);
		printf("%d\n",crc[x]);
	}
}