# **APCS Nov 2021 - g597 [Q3](https://zerojudge.tw/ShowProblem?problemid=g597) [Python]**
> 本題敘述：
> 有 `n` 台機器排成一直線, 每一個機器都有一個數值`t[i]`, 代表該台機器要產出一單位的資料需要`t[i]`單位的時間，接下來有 `m` 個工作要完成, 每一個工作都需要位置在`[l[i],r[i]]`的機器各生產出`w[i]`單位資料，現在你可以調換`n`台機器的順序, 目標是使得這`m`個工作做完的總時間要最小。

> [name=BlackInk7777]
這如果用迴圈慢慢加絕對會超時，所以要使用差分數組來讓這題快一點。

---

# 差分數組解釋：
假設我們有一個初始都為零的數組 dur，大小為 5，如下：
``Array= [0,0,0,0,0]``
假設要在`[2,5]`內所有元素上加 1、要在`[3,5]`內所有元素上加 2：

### 使用差分數組實現

1. **初始化差分數組 `diff`：**
`diff = [0, 0, 0, 0, 0, 0, 0]`
同樣，差分數組的大小是原數組大小加一。

2. **第一個區間 \([2, 4]\) 的加值：**
- 在位置 2 上加 1：`diff = [0, 0, 1, 0, 0, 0, 0]`
- 在位置 5 上減 1（位置 4 的下一個位置）：`diff = [0, 0, 1, 0, 0, -1, 0]`

3. **第二個區間 \([3, 5]\) 的加值：**
- 在位置 3 上加 2：`diff = [0, 0, 1, 2, 0, -1, 0]`
- 在位置 6 上減 2（位置 5 的下一個位置）：`diff = [0, 0, 1, 2, 0, -1, -2]`

4. **通過差分數組統計最終的 `dur` 數組：**
- 迴圈 `diff` 並更新 `dur`：
- \( i = 1 \)：`dur[1] = 0`。
- \( i = 2 \)：`dur[2] = 1`（累加得 1）。
- \( i = 3 \)：`dur[3] = 3`（累加得 1 + 2）。
- \( i = 4 \)：`dur[4] = 3`（累加得 3 + 0）。
- \( i = 5 \)：`dur[5] = 2`（累加得 3 - 1）。
- \( i = 6 \)：`dur[6] = 0`（累加得 2 - 2）。

### 結果
最終，`dur` 數組更新為：`dur = [0, 0, 1, 3, 3, 2]`

---

# 代碼實作

def main():
    n,m = map(int,input().split())
    dur = [0] * (n + 2)
    diff = [0] * (n + 2)

    for _ in range(m):
        l,r,w = map(int, input().split())
        diff[l] += w
        diff[r+1] -= w

    machine = [int(num) for num in input().split()]

    currect = 0

    for i in range(1 ,len(diff)):
        dur[i] = currect + diff[i]
        currect = dur[i]

    dur.pop(0)
    dur.pop()

    times = 0

    machine.sort(reverse=True)
    dur.sort()

    for i in range(len(dur)):
        times += dur[i] * machine[i]

    print(times)
    
if __name__ == "__main__":
    main()

**本題知識**
* **差分數組**

* **pop**用法：`[(這是陣列)].pop(位置)`

**Ex:**

    the_list = [0,1,2,3,4]
    the_list.pop(0) // output: [1,2,3,4]