Children Holiday

題目

有 $n$ $(1 \leq n \leq 1000)$ 個人要吹 $m$ $(0 \leq m \leq 15000)$ 顆氣球，每一個人吹一顆氣球要花 $t_i$ $(1 \leq t_i \leq 100)$ 分鐘。然而，每吹 $z_i$ $(1 \leq z_i \leq 1000)$ 顆氣球後他就需要休息 $y_i$ $(1 \leq y_i \leq 100)$ 分鐘。現在，請求出在最佳的工作分配下，需要花多少時間吹好 $m$ 顆氣球，以及每一個人分別要吹幾顆氣球。（如果一個人吹完最後一顆氣球後需要休息，則這次休息的時間不會被算在吹氣球的總時間）

解題思路

（這題比較複雜，需要注意的細節比較多，常見錯誤在下面會提到）

這題雖然答案是正整數，但直接枚舉的話時間複雜度還是太慢了。但是，這個題目一樣具有「單調性」，如果能在一個時間 $t$ 分鐘以內吹好所有氣球，時間比 $t$ 多也一定可以。如過不能在 $t$ 分鐘以內吹好所有氣球，時間比 $t$ 少也一定沒辦法。

利用二分搜尋，對於每一個花費時間用 $O(n)$ 判斷是否能夠吹滿 m 顆氣球，總時間複雜度為 $O(n \times log(m \times (t + y / z) / n))$，可以在時限內輸出答案。

常見錯誤

• 答案最多可以到差不多 $3e6$，$r$ 不能設太小
• 記得最後一次就算集滿 $z$ 次也不用加 $y$
• 如果是用有加 $y$ / 沒加 $y$ 分開處理的話，記得沒加 $y$（最後一次）最多只能加到 $z$（請見範例程式碼）
• 輸出答案的時候不要讓他們加起來超過 $m$（剛好到 $m$ 的時候剩下的就輸出 $0$）

完整程式碼

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

int main() {
    int n, m;
    cin >> m >> n;
    vector<int> z(n), y(n), t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> z[i] >> y[i];
    }
    int l = 0, r = 3e6;
    vector<int> finalwork(n);
    while (l < r) {
        int mid = (l + r) / 2;
        int cnt = 0;
        vector<int> work(n);
        for (int i = 0; i < n; i++) {
            int pre = cnt;
            cnt += mid / (t[i] * z[i] + y[i]) * z[i];
            cnt += min((mid % (t[i] * z[i] + y[i])) / t[i], z[i]);
            if (cnt >= m) {
                work[i] = m - pre;
                break;
            }
            work[i] = cnt - pre;
        }
        if (cnt < m) {
            l = mid + 1;
        }
        else {
            r = mid;
            finalwork = work;
        }
    }
    cout << l << "\n";
    for (int i = 0; i < n; i++) {
        cout << finalwork[i] << " ";
    }
    cout << "\n";
}