ZeroJudge 解題筆記：p925.鬆餅 (Waffle)

作者：王一哲
日期：2026年10月28日


ZeroJudge 題目連結：p925.鬆餅 (Waffle)

題目 pdf 檔連結：鬆餅 (Waffle)

解題想法

每組測資第一列為兩個整數，代表兩種口味鬆餅分別需要的烘烤時間 $t_i ~(1 \leq t_i \leq 20)$；第二列有一個正整數 $m$，代表有 $m$ 張訂單；接下來 $m$ 列每列有一個正整數，代表這張訂單的鬆餅口味。只有兩台鬆餅機，只計算烘烤時間，而且要按照訂單順序製作鬆餅，求完成所有訂單需要的最短時間。

這題用貪心法解題，假設兩台鬆餅機使用的時間分別為 $a, b$，讀取到一張新的訂單時由當時最快可用的鬆餅機製作，將這台鬆餅機使用的時間加上這個口味鬆餅的烘烤時間。完成所有的訂單之後，答案為 $a, b$ 較大的值。

題目 pdf 檔裡面說是多筆測資，但是 ZeroJudge 的測資似乎是單筆測資，如果用多筆測資的寫法反而會在測資 #4 遇到 Index out of range。如果加上檢查剩餘資料長度的防呆裝置，反而會變成多輸出一個題目沒有要求的文字 1。改成處理單筆測資的寫法才能 AC。

Python 程式碼

在測資 #4 遇到 Index out of range。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資
        time = [0] + list(map(int, data[ptr : ptr + 2]))
        ptr += 2
        m = int(data[ptr])
        ptr += 1
        a, b = 0, 0
        for _ in range(m):
            idx = int(data[ptr])
            ptr += 1
            if a <= b:
                a += time[idx]
            else:
                b += time[idx]
        
        result.append(f"{max(a, b):d}\n")
            
    # 一次輸出所有答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 13 ms，記憶體約為 9.5 MB，通過測試。

time = [0] + list(map(int, input().split()))
m = int(input())
a, b = 0, 0
for _ in range(m):
    idx = int(input())
    if a <= b:
        a += time[idx]
    else:
        b += time[idx]
        
print(max(a, b))

C++ 程式碼

在測資 #4 遇到 Index out of range。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int time[3] = {0};
    while(cin >> time[1] >> time[2]) {
        int m, a = 0, b = 0;
        cin >> m;
        for(int i = 0; i < m; i++) {
            int idx;
            cin >> idx;
            if (a <= b) a += time[idx];
            else b += time[idx];
        }
        cout << (a >= b ? a : b) << "\n";
    }
    return 0;
}

使用時間約為 2 ms，記憶體約為 3.5 MB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int time[3] = {0}, m;
    cin >> time[1] >> time[2] >> m;
    int a = 0, b = 0;
    for(int i = 0; i < m; i++) {
        int idx;
        cin >> idx;
        if (a <= b) a += time[idx];
        else b += time[idx];
    }
    cout << (a >= b ? a : b) << "\n";
    return 0;
}

C 語言程式碼

使用時間約為 1 ms，記憶體約為 1.6 MB，通過測試。

#include <stdio.h>

int main() {
    int time[3] = {0}, m;
    scanf("%d %d %d", &time[1], &time[2], &m);
    int a = 0, b = 0;
    for(int i = 0; i < m; i++) {
        int idx;
        scanf("%d", &idx);
        if (a <= b) a += time[idx];
        else b += time[idx];
    }
    if (a >= b) printf("%d\n", a);
    else printf("%d\n", b);
    return 0;
}