Children Holiday

題目

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

解題思路

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

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

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

常見錯誤

  • 答案最多可以到差不多 3e63e6rr 不能設太小
  • 記得最後一次就算集滿 zz 次也不用加 yy
  • 如果是用有加 yy / 沒加 yy 分開處理的話,記得沒加 yy(最後一次)最多只能加到 zz(請見範例程式碼)
  • 輸出答案的時候不要讓他們加起來超過 mm(剛好到 mm 的時候剩下的就輸出 00

完整程式碼

#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";
}