Codeforces 416B Art Union：流水線作業調度貪心解法

問題描述

有 n 位畫家、m 幅畫。畫家以流水線方式作業：第 j 位畫家處理第 i 幅畫需 t_ij 時間。規則：

1. 每幅畫必須按畫家順序 1→2→...→n 處理
2. 每位畫家按畫的順序 1→2→...→m 處理
3. 畫家同一時間只能處理一幅畫
4. 上一位畫家完成後，畫立即可交給下一位

求每幅畫完成的時間。

貪心解法

維護陣列 t[j] 記錄第 j 位畫家完成上一幅畫的時間。對每幅畫 i：

• 第 1 位畫家開始時間 = t[1]
• 第 j 位畫家開始時間 = max(t[j], 完成時間 of 畫家 j-1)
• 更新 t[j] 為該畫家完成本幅畫的時間

程式碼實作

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 50005;
int m, n, ans[N];

int main() {
    int v[10];
    memset(v, 0, sizeof(v));
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++) {
        int cur_time = 0, a;
        for (int j = 0; j < n; j++) {
            scanf("%d", &a);
            int start = max(v[j], cur_time);
            cur_time = start + a;
            v[j] = cur_time;
        }
        ans[i] = cur_time;
    }
    for (int i = 1; i < m; i++) printf("%d ", ans[i]);
    printf("%d\n", ans[m]);
    return 0;
}

複雜度分析

• 時間：O(m × n)，m ≤ 50000，n ≤ 5，極快
• 空間：O(n)