問題描述

N 張餅，第 i 張需 t_i 時間煎熟。M 個鍋可並行。每鍋同一時間只能煎一張餅，餅不可分割。求煎熟所有餅的最少時間。

貪心結論

答案 = max( ceil(Σt_i / M), max(t_i) )。

• Σt_i / M：總工作量除以並行度，理論下界。
• max(t_i)：最長單餅時間，不可並行縮短。
• 取較大者即為最優完成時間（多機器調度問題的經典下界，且對於不可分割任務在單機無釋放時間情況下可達到）。

代碼實現

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        long long sum = 0;
        int mx = 0;
        for (int i=0;i

關鍵細節

向上取整：(sum + m - 1) / m 避免浮點數。
長整型：sum 可能達 40000×40000 = 1.6e9，需 long long。
證明直覺：若最長任務 ≤ 平均負載，可通過列表調度（LPT 或任意順序）達到平均負載上界；若最長任務 > 平均負載，該任務決定完成時間。


複雜度

時間：O(N) 每測試用例。
空間：O(1)。


總結
ZOJ 3778 是「並行機器調度最小完工時間」的簡化版（無釋放時間、任務不可分割、無優先級）。答案為兩個下界的最大值，無需複雜調度算法。此結論對應經典結果：C_max ≥ max(Σp_i/m, max p_i)，且對於此模型下界可達。掌握此公式，同類「總量/並行度 vs 最大單任務」問題秒解。