10273 Eat or Not to Eat?

題目連結

題目敘述

一位年輕的農夫有 N 頭奶牛，但牠們產的牛奶量實在非常非常少
John 無法僅靠這些少量的牛奶維生
所以他打算吃掉其中「表現最差」的幾頭牛以度過饑餓
每天 John 會選出當天產奶量最少的那頭牛並將其吃掉
如果當天有多頭牛並列為最低產奶量
John 會因為猶豫不決而不會吃任何牛（耶！太好了！）。

第 i 頭牛的產奶週期為 Ti
也就是說，若牠在某天產了 L 單位的牛奶
那麼在 Ti 天後，若牠尚未被吃掉
將會再度產 L 單位的牛奶。

雖然 John 並不聰明
但他懷疑所有牛最終是否都會被吃光，因此請你幫助他
別忘了，他會提供一些美味的牛肉作為回報！

輸入說明

輸入的第一行包含一個整數 T，表示測試案例的數量（1 ≤ T ≤ 50）。
每個測試案例先有一行整數 N（1 ≤ N ≤ 1000），代表奶牛的數量。
接下來有 N 行，對應第 i 頭牛：

• 首先是一個整數 Ti（1 ≤ Ti ≤ 10），表示該頭牛的產奶週期；
• 接著有 Ti 個整數 Mj（0 ≤ Mj ≤ 250），分別表示該頭牛在週期內第 j 天所能產的牛奶量。

輸出說明

對於每個測試案例，輸出一行，包含兩個整數 C、D：

• C：最終不會被吃掉的奶牛數量；
• D：當最後一頭被吃掉的牛被吃掉時，已經過的天數。

若沒有任何奶牛被吃掉，則第二個數字請輸出 0。

程式碼

#include <bits/stdc++.h>
using namespace std;

#define INF LONG_LONG_MAX/1000
#define int long long

signed main() {
    int t; cin >> t;
    while (t--) {
        int n, m, tmp;
        cin >> n; // 讀取牛隻總數 N
        vector<vector<int>> v(n); // 使用二維陣列 v 存放每頭牛的週期性生產量
        for (int i = 0; i < n; i++) {
            cin >> m; // 讀取第 i 頭牛的生產週期長度 Ti
            while (m--) {
                cin >> tmp; // 讀取週期中某一天的產量
                v[i].push_back(tmp); // 將該天產量加入第 i 頭牛的資料陣列
            }
        }

        // lastday：最後一次宰殺動作發生的天數（0-base）
        // cnt：已宰殺牛隻總數
        int lastday = -1, cnt = 0;
        vector<int> kill(n); // kill[i] = 1 表示第 i 頭牛已被宰殺，否則為 0
        for (int day = 0; day - lastday <= 2520; day++) { // 模擬每日作業，終止條件：自上次宰殺日起連續 2520 天（Ti 跟 Mj 的最小公倍數）內未再發生宰殺
            int mn = INF; // 當日檢測到的最小產量
            int cowID = -1; // 對應最小產量的牛隻索引
            for (int i = 0; i < n; i++) { // 遍歷所有尚未被宰殺的牛隻，尋找當日唯一最少產量
                if (kill[i]) continue; // 牛被殺掉就跳過
                int milk = v[i][day%v[i].size()]; // 以 day % 週期長度 取當日產量
                if (milk < mn) { // 發現更小產量時，更新最小值及對應牛隻索引
                    mn = milk;
                    cowID = i;
                }
                else if (milk == mn) cowID = -1; // 若有多頭牛隻產量相同且為最小，標註為無法確定唯一最少
            }
            if (~cowID) { // 若存在唯一最少產量的牛隻，則進行宰殺動作
                kill[cowID] = 1; // 標記該牛隻已被宰殺
                lastday = day; // 更新最後一次宰殺的天數索引
                cnt++; // 累計宰殺數量
            }
        }
        cout << n-cnt << ' ' << lastday+1 << '\n'; // 最後輸出
    }
}