k514 - P2.解藥 (Medicine)

🔗 前往 ZeroJudge 原題

題目描述

題目給定四種藥品的倍數，以及每種藥品擁有的藥丸編號。目標是找到一個數字 c，使得 c 能夠被四種藥品的倍數所包含，並且這個數字是四種藥品中擁有藥丸編號最小的那個。如果找不到這樣的數字，則輸出 -1。

解題思路

程式碼首先讀取四種藥品的倍數 a[0] 到 a[3]，並記錄下擁有藥丸編號的藥品種類 t。接著，讀取每種藥品擁有的藥丸編號，並儲存在二維陣列 b[i][x] 中，其中 b[i][x] = 1 表示藥品 i 擁有藥丸編號 x。

程式碼從 1 開始迭代，直到 100。對於每個數字 i，檢查藥品 t 是否擁有藥丸編號 i。如果擁有，則計算 c = i，並檢查 c 是否能夠被四種藥品的倍數所包含。具體來說，對於每種藥品 j，檢查 a[j] * c 是否小於等於 100，並且藥品 j 是否擁有藥丸編號 a[j] * c。如果 c 能夠被四種藥品的倍數所包含，則輸出 a[j] * c，並結束程式。

如果迭代到 100 仍然找不到符合條件的數字，則輸出 -1。

複雜度分析

• 時間複雜度: O(n * 100 * 4) = O(n)，其中 n 是輸入的藥丸數量。最壞情況下，需要遍歷所有可能的藥丸編號 (1 到 100)，並檢查每種藥品是否擁有該編號。
• 空間複雜度: O(4 * 101) = O(1)，因為二維陣列 b 的大小是固定的。

程式碼

#include <iostream>
using namespace std;
int a[4],b[4][101],n,x,ans,t;
int main(){
	for(int i=0;i<4;++i){
		cin >> a[i];
		if(a[i]==1)t=i;
	}
	cin >> n;
	for(int i=0;i<4;++i){
		for(int j=0;j<n;++j){
			cin >> x;
			b[i][x]=1;
		}
	} 
	for(int i=1;i<=100;++i){
		if(b[t][i]){
			int c=i,ct=0;
			for(int j=0;j<4;++j){
				if(a[j]*c<=100&&b[j][a[j]*c]){
					++ct;
				}
			}
			if(ct==4){
				for(int j=0;j<4;++j){
					if(a[j]*c<=100&&b[j][a[j]*c]){
						cout << a[j]*c<< " ";
					}
				}
				return 0;
			}
		}
	}
	cout << "-1";
}