【題解】Zerojudge g597 - 3. 生產線

題目連結

題目大意

有 $n$ 台機器和 $m$ 個工作。第 $i$ 台機器產生 $1$ 單位的資料需要花費 $t_i$ 單位的時間。完成第 $j$ 個工作需要位置落在 $L_j \sim R_j$ 的機器都產生 $w_j$ 單位的資料。你現在可以調換機器的順序，問最少需要花費多少時間才能完成所有工作？

• $1 \leq n, m \leq 2 \cdot 10^5$

題解

假設我們把第 $i$ 台機器放在某個位置 $p$，這台機器完成工作的總時間會是滿足 $L_j \leq p \leq R_j$ 的所有工作的 $w_j$ 總和。我們可以先計算出每個位置需要產生多少單位的資料，並把需要較多的資料分配給產生資料比較快的機器 ($\sum w_j$ 大的配 $t_i$ 比較小的)。計算每個位置的總產量需要區間加值，但由於查詢都在加值後面，我們可以直接用差分 + 前綴和維護，並不需要線段樹或 BIT 等資料結構。其他實作的細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> f(n + 1);
	for(int i = 0; i < m; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		l--;
		f[l] += x;
		f[r] -= x;
	}
	for(int i = 1; i <= n; i++) {
		f[i] += f[i - 1];
	}
	f.pop_back();
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(f.begin(), f.end());
	sort(a.rbegin(), a.rend());
	long long ans = 0;
	for(int i = 0; i < n; i++) {
		ans += f[i] * a[i];
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge g597 - 3. 生產線