g597 - 3. 生產線
題目描述
題目要求在有 $n$ 台機器和 $m$ 個工作的生產線上，找到最佳的機器排列順序，以最小化完成所有工作的總時間。每個工作需要在指定範圍 $[l_i, r_i]$ 的機器上生產 $w_i$ 單位資料，每台機器生產單位資料所需時間不同。
解題思路
本題的核心思路是利用貪心法和排序。首先，將工作按照起始位置排序。然後，遍歷機器，並使用優先佇列維護當前可用的機器。對於每個機器，將其加入優先佇列，並計算當前位置的總生產能力。接著，遍歷每個工作，並將其所需的生產量分配給生產能力最高的機器。最後，將機器的生產時間按照降序排列，並與工作的價值（生產量）配對，以最小化總時間。
具體步驟如下：
- 讀取輸入，包括機器數量 $n$、工作數量 $m$ 以及每個工作的工作範圍和生產量。
- 將工作按照起始位置 $l_i$ 排序。
- 遍歷機器，將每個機器加入優先佇列，優先佇列按照生產能力（時間）降序排列。
- 計算每個位置的總生產能力，使用前綴和儲存。
- 讀取每個機器的生產時間 $t_i$。
- 將機器的生產時間和總生產能力排序。
- 將機器的生產時間按照降序排列，並與工作的價值（生產量）配對，計算總時間。
複雜度分析
- 時間複雜度: O(m log m + n log n + n log n) (排序工作和機器，以及優先佇列操作)
- 空間複雜度: O(n + m) (儲存工作和機器的陣列，以及優先佇列)
程式碼
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
long n,m,v,ans,it,c[200005],b[200005];
pair <long ,pair <long,long> > a[200005];//begin,end,v
priority_queue <pair <long,long> > p;//end,begin,v
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<m;++i){
cin >> a[i].first >> a[i].second.first >> a[i].second.second;
}
sort(a,a+m);
for(int i=1;i<=n;++i){
while(it<m&&a[it].first<=i){
v+=a[it].second.second;
p.push({-a[it].second.first,a[it].second.second});
++it;
}
c[i]=v;
while(p.empty()==0&&-p.top().first==i){
v-=p.top().second;
p.pop();
}
}
for(int i=1;i<=n;++i){
cin >> b[i];
}
sort(b+1,b+n+1);
sort(c+1,c+n+1);
for(int i=n,j=1;i>=1;--i,++j){
ans+=b[i]*c[j];
}
cout << ans;
}