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';  // 最後輸出
  }
}