列印工廠 題解|APCS 2025 年 11 月高級 第 2 題
前置知識
這題要把下面兩個技巧組合起來,講解直接把它們當成已知,沒讀過的先讀:
- 枚舉排列:NTUCPC Guide〈枚舉〉——
next_permutation可以把 \(n\) 個東西的全部 \(n!\) 種順序一個一個產生出來。 - 二分搜答案:NTUCPC Guide〈對答案二分搜〉——「空檔至少 \(g\) 做不做得到」有單調性(\(g\) 可以,比它小的也都可以),就能二分搜最大的可行 \(g\)。吳邦一《AP325》第 2 章「排序與二分搜」也有講。
簡潔題意
\(n\) 個工作,工作 \(i\) 不得早於 \(s_i\) 開始、要連續做 \(t_i\) 單位時間、必須在 \(d_i\) 以前(含)完成,工作不能重疊。可以自由安排順序與開始時間,求最大的整數 \(g\),使每兩個相鄰工作之間都至少空 \(g\) 單位時間;第一件之前、最後一件之後的空檔不算(\(2 \le n \le 8\),\(0 \le s_i < d_i \le 1000\),\(1 \le t_i \le d_i - s_i\),保證 \(g = 0\) 時排得出來)。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(30\) 分):\(n \le 3\)。
- 子題組 2(\(70\) 分):無額外限制。
三件事拆開來做
這題乍看要同時決定順序、開始時間、還有 \(g\),拆成三層就很清楚:
- 固定順序、固定 \(g\):每一件都盡早開工——開始時間取 \(\max(s_i,\ \text{上一件完工時間} + g)\)(第一件不用等 \(g\)),完工時間超過 \(d_i\) 就是這個順序做不到。盡早開工一定不吃虧:越早完工,下一件能選的開始時間只會更多。
- 順序怎麼決定:\(n \le 8\),\(8! = 40320\) 種順序全部試一遍就好。子題組 1 的 \(n \le 3\) 只有 \(6\) 種,就是在提示這一點。
- \(g\) 怎麼決定:\(g\) 可行則更小的 \(g\) 也可行,在 \(0 \sim 1000\) 之間二分搜最大的可行值(從 \(0\) 往上一個一個試到第一個不行為止也來得及,本題 \(1000 \times 40320 \times 8 \approx 3 \times 10^8\) 次簡單運算)。
總共 \(\log_2 1000 \approx 10\) 次判定、每次 \(40320 \times 8\) 步,瞬間完成。同一份程式子題組 1 和子題組 2 都適用。
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int s[8], d[8], t[8];
int order[8]; // 一種工作順序(工作編號的排列)
// 照 order 的順序、每件都盡早開工,相鄰工作之間至少空 g,能不能全部準時?
bool order_ok(int g) {
int finish = 0; // 上一件的完工時間
for (int idx = 0; idx < n; idx++) {
int job = order[idx];
int start = s[job];
if (idx > 0) start = max(start, finish + g); // 第一件之前不用空 g
finish = start + t[job];
if (finish > d[job]) return false;
}
return true;
}
// 空檔至少 g 的話,有沒有任何一種順序做得到?
bool feasible(int g) {
for (int i = 0; i < n; i++) order[i] = i;
do {
if (order_ok(g)) return true;
} while (next_permutation(order, order + n));
return false;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i] >> d[i] >> t[i];
// 題目保證 g = 0 可行;g 越大越難達成,二分搜最大的可行 g
int low = 0, high = 1000;
while (low < high) {
int mid = (low + high + 1) / 2;
if (feasible(mid)) low = mid;
else high = mid - 1;
}
cout << low << '\n';
return 0;
}
延伸:工作再多一點就換位元 DP
如果 \(n\) 到 \(15 \sim 20\),\(n!\) 就不行了。固定 \(g\) 之後,令 dp[mask] 為「做完 mask 這些工作(其他還沒做)最早幾點能完工」:從 dp[mask] 接著做一件還沒做的工作 \(i\),盡早開工算出完工時間,不超過 \(d_i\) 就更新 dp[mask | (1 << i)]。為什麼同一個集合只留最早完工時間就夠?剩下要做哪些工作只由集合決定,較早完工的狀態可以等到跟較晚的一樣再開始,所以較晚的不可能更好。全集可達就代表這個 \(g\) 可行,再套外層的二分搜。時間 \(O(2^n \cdot n \cdot \log 1000)\)。
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
int n;
int s[8], d[8], t[8];
int dp[1 << 8]; // dp[mask]:做完 mask 裡的工作(其他還沒做)最早幾點能完工
bool feasible(int g) {
for (int mask = 0; mask < (1 << n); mask++) dp[mask] = INF;
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == INF) continue;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) continue; // 工作 i 已經做過
int start = s[i];
if (mask != 0) start = max(start, dp[mask] + g); // 第一件之前不用空 g
int finish = start + t[i];
if (finish > d[i]) continue;
dp[mask | (1 << i)] = min(dp[mask | (1 << i)], finish);
}
}
return dp[(1 << n) - 1] != INF;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i] >> d[i] >> t[i];
int low = 0, high = 1000;
while (low < high) {
int mid = (low + high + 1) / 2;
if (feasible(mid)) low = mid;
else high = mid - 1;
}
cout << low << '\n';
return 0;
}
測過再交:範例都只有三件工作
兩個範例都是 \(n = 3\),答案是 \(5\) 和 \(0\)。沒蓋到的:\(n\) 比 \(3\) 大、答案很大,還有一種兩個範例都會過的錯法(只試截止時間早的先做,見常犯錯誤)——第 1 列就是抓它的。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
3 / 0 4 1 / 4 5 1 / 1 3 1 |
1 |
要照工作 \(1, 3, 2\) 的順序做;截止時間最早的工作 \(3\) 先做,工作 \(1\)、\(2\) 之間就擠不出空檔 |
2 / 0 1 1 / 999 1000 1 |
998 |
答案很大:二分搜(或從 \(0\) 往上試)的範圍要開到 \(1000\) |
8 / 0 1000 1(同一行重複 \(8\) 次) |
141 |
\(n = 8\):\(8\) 件工作、\(7\) 個空檔,\(8 + 7g \le 1000\) |
三筆都親眼看過正確,這題就穩了。
常犯錯誤
- 只試「截止時間早的先做」這一種順序:這是排程題常見的貪心,但有開始時間限制時不對。範例全過;自測表第 1 列會印
0,本站 \(20\) 筆掛 \(8\) 筆。 - 第一件之前也空 \(g\)(「上一件完工時間」一開始是 \(0\),第一件也照 \(\max(s_i,\ 0 + g)\) 算):題目說第一件之前的空檔不算。範例 1 就會印
3。