開啟章節選單
Children Holiday
題目
有 個人要吹 顆氣球,每一個人吹一顆氣球要花 分鐘。然而,每吹 顆氣球後他就需要休息 分鐘。現在,請求出在最佳的工作分配下,需要花多少時間吹好 顆氣球,以及每一個人分別要吹幾顆氣球。(如果一個人吹完最後一顆氣球後需要休息,則這次休息的時間不會被算在吹氣球的總時間)
解題思路
(這題比較複雜,需要注意的細節比較多,常見錯誤在下面會提到)
這題雖然答案是正整數,但直接枚舉的話時間複雜度還是太慢了。但是,這個題目一樣具有「單調性」,如果能在一個時間 分鐘以內吹好所有氣球,時間比 多也一定可以。如過不能在 分鐘以內吹好所有氣球,時間比 少也一定沒辦法。
利用二分搜尋,對於每一個花費時間用 判斷是否能夠吹滿 m 顆氣球,總時間複雜度為 ,可以在時限內輸出答案。
常見錯誤
- 答案最多可以到差不多 , 不能設太小
- 記得最後一次就算集滿 次也不用加
- 如果是用有加 / 沒加 分開處理的話,記得沒加 (最後一次)最多只能加到 (請見範例程式碼)
- 輸出答案的時候不要讓他們加起來超過 (剛好到 的時候剩下的就輸出 )
完整程式碼
#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"; }