【題解】ZeroJudge e520: 13190 – Rockabye Tobby

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e520
【解題想法】

  • 想找出每種藥物服用時間的最小公因數,當成時間累進的最小單位。
  • 時間刻度每前進一格,就檢查每一種藥物是否該服用,直到滿足須服用的最少藥物數量。
#include <iostream>
using namespace std;

int myGCD(int x, int y){
    while ((x%=y) && (y%=x));
    return x+y;
}

int main() {
    int T, n, k;
    cin >> T;
    while (T--){
        cin >> n >> k;
        string m[n];
        int f[n];
        for (int i = 0; i < n; i++){
            cin >> m[i] >> f[i];
        }
        int D = f[0];
        for (int i = 1; i < n; i++){
            D = myGCD(D, f[i]);
        }
        int Time = D, cnt = 0;
        while (cnt < k){
            for (int i = 0; i < n && cnt < k; i++){
                if (Time % f[i] == 0){
                    cout << Time << " " << m[i] << "\n";
                    cnt++;
                }
            }
            Time += D;
        }
    }
    return 0;
}
分享本文 Share with friends