# APCS實作題2021年11月第3題：生産線

> 日期：2024年7月31日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g597)

## 題目

### 問題描述

有 $n$ 台機器排成一直線，每一個機器都有一個數值 $t[i]$，代表該台機器要產出一單位的資料需要 $t[i]$ 單位的時間。
接下來有 $m$ 個工作要完成，每一個工作都需要位置在 $l[i], r[i]$ 的機器各生產出 $w[i]$ 單位資料。
現在你可以調換 $n$ 台機器的順序，目標是使得這 $i$ 個工作做完的總時間要最小。
<br />

### 輸入說明

先輸入兩個正整數 $n$ 和 $m$ 代表有 $n$ 台機器和 $m$ 個工作。
接下來有 $m$ 行，每行有三個正整數 $l[i], r[i], w[i]$，代表第 $i$ 個工作需要編號從 $l[i]$ 到 $r[i]$ 的機器完成，並且需要各產生出 $w[i]$ 單位的資料。
最後一行包含 $n$ 個正整數 $t[1], t[2], \dots, t[n]$。

數字範圍
- $1 \leq n, m \leq 200000$
- $1 \leq w[i] \leq 100$
- $1 \leq t[i] \leq 100$
- $1 \leq l[i] \leq r[i] \leq n$

子題配分
- 30%：$1 \leq n, m \leq 100, ~ w[i] = 1$
- 30%：$w[i] = 1$
- 40%：無額外限制

<br />

### 輸出格式

輸出最小的總花費時間
<br />

### 範例輸入1

5 1
2 4 1
1 2 3 4 5

### 範例輸出1

6

### 範例輸入2

10 3
2 5 6
3 6 4
7 8 1
1 2 3 4 5 6 7 8 9 10

### 範例輸出2

117

<br /><br />

## 解題的基本想法

如果想要得到最短的工作時間 time，需要使用産生1單位資料需時最短的機器處理最多的工作量。因此要先計算每部機器的工作量 loads，再將 loads 由小到大排序；再將機器依照産生1單位資料需要的時間 $w[i]$ 由大到小排序；將每部機器的工作量乘以需要的時間計算每部機器的工作時間 $t[i] = loads[i]*w[i]$，再加總 $t[i]$ 就是答案 time。
<br /><br />

## Python 程式碼

### 寫法1，讀取資料時用迴圈計算每部機器的工作量，會超時

由於第6、7行多了一組迴圈，到第6筆測資時會超時。

n, m = map(int, input().split())  # 機器數量n、工作數量 m
loads = [0]*(n+1)  # 每部機器的工作量，由於機器編號是 1 ~ n，串列長度要開 n+1

for _ in range(m):  # 讀取 m 行資料
    l, r, w = map(int, input().split())  # 左側機器編號 l，右側機器編號 r，工作量 w
    for i in range(l, r+1):  # 更新第l到r機器的工作量，這兩行導致程式超時
        loads[i] += w

machines = list(map(int, input().split()))  # 每部機器産生1單位資料需要的時間
machines.sort(reverse=True)  # 機器由大到小排序
loads = loads[1:]  # 刪除編號為0的機器
loads.sort()  # 每部機器工作量由小到大排序
time = 0  # 答案，總工作時間
for load, machine in zip(loads, machines):  # 計算答案
    time += load*machine

print(time)  # 印出答案

<br /><br />

### 寫法2，利用差分數組計算每部機器的工作量

網路上找到的差分數組教學〈[小而美的算法技巧：差分数组](https://labuladong.online/algo/data-structure/diff-array/)〉。基本上就是記錄第$i$筆資料與第$i-1$筆資料的差值，如果 $[l, r]$ 區間的數值要加上 $w$，則差分數組 $diff[l] += w$，$diff[r+1] -= w$。
第18筆測資費時最久約為 1.1 s，使用記憶體最多約為 52 MB，通過測試。

n, m = map(int, input().split())  # 機器數量n、工作數量 m
diff = [0]*(n+2)  # 差分數組，長度要是對應的陣列長度加1
loads = [0]*(n+2)  # 每部機器的工作量，機器編號是 1 ~ n，配合 diff 要開 n+2

for _ in range(m):  # 讀取 m 行資料
    l, r, w = map(int, input().split())  # 左側機器編號 l，右側機器編號 r，工作量 w
    diff[l] += w  # 更新差分數組，[l, r] 區間工作量加 w
    diff[r+1] -= w  

cur = 0  # 目前讀取的 loads 數值
for i in range(1, n+2):  # 依序産生 1 ~ n+1
    loads[i] = cur + diff[i]  # 更新 loads[i]
    cur = loads[i]  # 更新 cur

machines = list(map(int, input().split()))  # 每部機器産生1單位資料需要的時間
machines.sort(reverse=True)  # 機器由大到小排序
loads = loads[1:-1]  # 刪除編號為 0 及 n+1 的機器
loads.sort()  # 每部機器工作量由小到大排序
time = 0  # 答案，總工作時間
for load, machine in zip(loads, machines):  # 計算答案
    time += load*machine

print(time)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，讀取資料時用迴圈計算每部機器的工作量，會超時

答案會超過 int 的上限，要用 long。由於第13行多了一組迴圈，到第10筆測資時會超時。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, m; cin >> n >> m;  // 機器數量n、工作數量 m
    vector<long> loads (n+1, 0);  // 每部機器的工作量，由於機器編號是 1 ~ n，串列長度要開 n+1

    for(int i=0; i<m; i++) {  // 讀取 m 行資料
        int l, r, w; cin >> l >> r >> w;  // 左側機器編號 l，右側機器編號 r，工作量 w
        for(int j=l; j<=r; j++) loads[j] += (long)w;  // 更新第l到r機器的工作量，此行導致程式超時
    }
    
    vector<int> machines (n, 0);  //  每部機器産生1單位資料需要的時間
    for(int i=0; i<n; i++) cin >> machines[i];
    sort(machines.begin(), machines.end(), greater<>());  // 機器由大到小排序
    loads.erase(loads.begin());  // 刪除編號為0的機器
    sort(loads.begin(), loads.end());  // 每部機器工作量由小到大排序
    long time = 0;  // 答案，總工作時間
    for(int i=0; i<n; i++) time += loads[i]*(long)machines[i];  // 計算答案

    cout << time << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，利用差分數組計算每部機器的工作量

費時最久約為 0.1 s，使用記憶體最多約為 4.2 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, m; cin >> n >> m;  // 機器數量n、工作數量 m
    vector<long> diff (n+2, 0);  // 差分數組
    vector<long> loads (n+2, 0);  // 每部機器的工作量

    for(int i=0; i<m; i++) {  // 讀取 m 行資料
        int l, r; cin >> l >> r;  // 左側機器編號 l，右側機器編號 r
        long w; cin >> w;  // 工作量 w
        diff[l] += w; diff[r+1] -= w; // 更新差分數組
    }
    
    long cur = 0;  // 目前讀取到的 loads[i] 數值
    for(int i=1; i<=n+1; i++) {  // 用差分數組計算每部機器的工作量
        loads[i] = cur + diff[i];
        cur = loads[i];
    }
    
    vector<int> machines (n, 0);  //  每部機器産生1單位資料需要的時間
    for(int i=0; i<n; i++) cin >> machines[i];
    sort(machines.begin(), machines.end(), greater<>());  // 機器由大到小排序
    loads.erase(loads.begin());  // 刪除編號為0的機器
    loads.pop_back();  // 刪除最後一部多出來的機器
    sort(loads.begin(), loads.end());  // 每部機器工作量由小到大排序
    long time = 0;  // 答案，總工作時間
    for(int i=0; i<n; i++) time += loads[i]*(long)machines[i];  // 計算答案

    cout << time << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

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