同題:UVa 13190 – Rockabye Tobby
“Rockabye baby, don’t you cry.”
Tobby非常擅長傳接球,他非常喜歡這個遊戲,有一天他決定出去玩,即使當時正在下雨。
他玩了很長時間,除了傳接球很多次之外,還順便生了病,有夠丟臉,真是可悲。
這就是為什麼現在他的母親 (Big Doggie) 在照顧他,除了唱那首美麗的搖籃曲 (Rockabye),還在指定時間準備好藥給他吃。
在醫生的醫療處方中,指定了藥物名稱以及多久服用一次。
醫生告訴他,如果他按照醫囑服藥,服用 K 個藥後他就會好起來。
Tobby 不喜歡生病(實際上沒人喜歡),所以他向母親保證他會按時吃藥。
這就是為什麼他現在想知道,他必須服用的前 K 個藥物是哪些,才能使他好起來,並且能在下雨天繼續去傳接球。
你能幫他嗎?
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入從包含一個整數 T (1 ≤ T ≤ 15),代表 Case 的數量。 對於每個 Case 包含兩個整數 N (1 ≤ N ≤ 3*103)和 K (1 ≤ K ≤ 104) N 代表醫生發送的藥物數量,K 代表 Tobby 必須服用的最少藥物數量。 接下來的 N 行,每行包含一個字串 M,一個整數 F (1 ≤ F ≤ 3*103)。 M 代表藥物名稱 (1 ≤ M 長度 ≤ 15),F 代表服用頻率。 藥物是根據其優先級列出的,即第一種是最重要的藥物,最後一種是最不重要的藥物。 | 對於每個 Case,輸出必須有k行,每行形式為「t m」。 「t m」表示在 t 時刻 Tobby 必須服用藥物 m。 如果必須在同一時間 t 服用兩種或兩種以上藥物,則應根據其優先級進行輸出。 |
1 2 5 Acetaminophen 20 Loratadine 30 | 20 Acetaminophen 30 Loratadine 40 Acetaminophen 60 Acetaminophen 60 Loratadine |
解題思路
使用 Vector 和 Pair 將藥物的名稱及服用頻率存起來,並用 While迴圈 來判斷目前的時間是否有需要服用的藥物 (可以被服用頻率整除)。需要注意的是只要服用了一種藥物就需要判斷目前服用的藥物數量是否有等於 K,如果有的話就需要將迴圈 Break 掉。
範例程式碼-ZeroJudge E520: Rockabye Tobby
#include <iostream>
#include <vector>
using namespace std;
pair<string, int> rtn (string name, int time)
{
pair<string, int>tmp;
tmp.first = name;
tmp.second = time;
return tmp;
}
int main() {
int N;
cin >> N;
for (int i = 0; i<N; i++)
{
int med, K;
cin >> med >> K;
vector<pair<string, int>>v;
for (int j = 0; j<med; j++)
{
string name;
int time;
cin >> name >> time;
v.push_back(rtn(name, time));
}
int count = 0, j = 1;
while (count < K)
{
for (auto it:v)
{
if (j % it.second == 0)
{
cout << j << " " << it.first << "\n";
count++;
if (count >= K) break;
}
}
j++;
}
}
}
//ZeroJudge E520
//Dr. SeanXD