---
# System prepended metadata

title: g597. 3. 生產線
tags: [greedy, APCS, 差分數組]

---

link：https://zerojudge.tw/ShowProblem?problemid=g597

### 想法
1. 題目要求最少時間做完，因此我們應該要讓做最快的機器處理最多單位的工作
2. 因此，我們在讀輸入時，就應該將指定區間 ( 題目給定 $l$ ~ $r$ )加上單位數 ( $w$ )。此外，由於牽涉到多次的區間加減，使用 **差分數組** 的方法來加速。
3. 最後將生產總單位數的 vector 由大到小排序；機器則按照生產時間由小到大排序，即可得到答案。

```C++=
#include <bits/stdc++.h>
using namespace std;

bool cmp(long long int &a, long long int &b) {
    return a > b;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    int l,r,w;
    cin>>n>>m;
    vector<long long int> works_diff(n,0); //可以用差分數組來寫區間和
    vector<long long int> works(n,0);
    vector<long long int> times(n);
    for (int i=0;i<m;i++){
        cin>>l>>r>>w;
        works_diff[l-1]+=w;
        works_diff[r]-=w;
    }
    for (int i=0;i<n;i++){
        if (i==0) works[i] = works_diff[i];
        else {
            works[i] = works[i-1]+works_diff[i];
        }
    }
    sort(works.begin(),works.end(),cmp);
    
    for (int i=0;i<n;i++){
        cin>>times[i];
    }
    sort(times.begin(),times.end());

    long long int ans = 0;
    for (int i=0;i<n;i++){
        ans+=works[i]*times[i];
    }
    cout<<ans;
}
```