# APCS實作題2025年11月高級第2題：列印工廠

> 第1版：2025年11月18日
> 第2版：2025年11月24日，更正標題，這題是 APCS **高級**實作題，不是中高級，我之前弄錯了。
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=r627)

<br />

## 解題想法

這題的測資不大，先産生所有工作的排序方式，再用二分搜尋法對每一種工作排序方式找出最長的休息時間。如果要産生所有的排序方式，在 Python 可以用 itertools.permutations； 在 C++ 可以先排序，再用 algorithm 函式庫的 next_permutation 産生下一種排序方式。
<br /><br />

## Python 程式碼

使用時間約為 0.8 s，記憶體約為 3.1 MB，通過測試。

from itertools import permutations

n = int(input())  # n 項工作
tasks = [list(map(int, input().split())) for _ in range(n)]  # 工作開始、截止、執行時間

ans = 0  # 答案
for perm in permutations(tasks):  # 枚舉所有工作排序方式
    low, high = 0, 1000  # 下限、上限
    while low <= high:  # 對答案二分搜
        mid = (high + low) // 2
        last = 0  # 最早開始時間
        flag = True  # 休息時間為 mid 是否可以完成所有的工作
        for i in range(n):  # 依序檢查每項工作
            s, d, t = perm[i]  # 第 i 項工作開始、截止、執行時間
            if i > 0: last += mid  # 不是首項工作，last 加上 mid
            last = max(last, s)  # 如果工作開始時間更晚，last 改為 s
            if last + t > d:  # 無法在截止時間之前完成工作
                flag = False
                break
            last += t  # 更新 last
        if flag:  # 如果休息時間為 mid 可以完成所有工作
            ans = max(ans, mid)  # 更新 ans
            low = mid + 1  # 提高 low，用更長的休息時間再測試
        else:  # 無法完成所有工作
            high = mid - 1  # 降低 high，用更短的休息時間再測試
""" 測試完所有的工作排序方式，印出答案 """
print(ans)

<br /><br />

## C++ 程式碼

使用時間約為 7 ms，記憶體約為 312 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // n 項工作
    vector<vector<int>> tasks (n, vector<int> (3, 0));  // (開始, 結束, 所需時間)
    for(int i=0; i<n; i++) {
        scanf("%d %d %d", &tasks[i][0], &tasks[i][1], &tasks[i][2]);
    }
    sort(tasks.begin(), tasks.end());  // 排序
    int ans = 0;  // 答案
    do {
        int low = 0, high = 1000;  // 下限、上限
        while(low <= high) {  // 對答案二分搜
            int mid = (high - low) / 2 + low;  // 中間值
            int last = 0;  // 最近一次工作的開始時間
            bool flag = true;  // 是否能完成所有的工作
            for(int i=0; i<n; i++) {  // 依序檢查所有的工作
                int s = tasks[i][0], d = tasks[i][1], t = tasks[i][2];
                if (i > 0) last += mid;  // 不是首項工作，加上休息時間
                last = max(last, s);  // 時間要取 last 及 s 較大者
                if (last + t > d) {  // 無法在截止時間前完成
                    flag = false;
                    break;
                }
                last += t;
            }
            if (flag) {  // 休息時間為 mid 可以完成所有的工作
                low = mid + 1;  // 提高 low
                ans = max(ans, mid);  // 更新 ans
            } else {  // 反之，降低 high
                high = mid - 1;
            }
        }
    } while(next_permutation(tasks.begin(), tasks.end()));  // 改變排序
    printf("%d\n", ans);
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`C++`、`Python`