e520 - 13190 - Rockabye Tobby

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Tobby 生病後需要按時服藥的情況。給定 n 種藥物，每種藥物都有名稱和服用頻率，以及需要服用的藥物數量 k。要求輸出 Tobby 需要服用的前 k 種藥物及其服用時間。如果多種藥物在同一時間需要服用，則按照藥物在輸入中的順序（優先級）輸出。

解題思路

這題可以使用模擬的方法來解決。我們需要模擬時間的流逝，並檢查每種藥物是否在當前時間需要服用。如果某種藥物在當前時間需要服用，則輸出該藥物及其服用時間，並減少需要服用的藥物數量 k。當 k 減少到 0 時，表示已經找到了需要服用的前 k 種藥物，可以停止模擬。

具體來說，我們使用一個迴圈來模擬時間的流逝，每次迴圈增加時間 d。然後，我們遍歷所有藥物，檢查 d 是否是該藥物服用頻率的倍數。如果是，則輸出該藥物及其服用時間，並減少 k。如果 k 減少到 0，則跳出迴圈。

複雜度分析

• 時間複雜度: O(n * k)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
struct m{
	string name;
	int t;
};
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int t,n,k;
	cin >> t;
	while(t--){
		cin >> n >> k;
		int d=0;
		m a[n];
		for(int i=0;i<n;++i)
			cin >> a[i].name >> a[i].t;
		while(k){
			++d;
			for(int i=0;i<n;++i){
				if(d%a[i].t==0){
					cout << d << " " << a[i].name << "\n";
					--k;
				}
				if(k==0){
					break;
				}
			}
		} 
	}
}