LOJ #6035. 「雅禮集訓 2017 Day4」洗衣服

題目連結：傳送門

用優先隊列處理出洗完所有衣服的最小時間

處理出晾幹所有衣服的最小時間

分别用 f 1 f1 f1， f 2 f2 f2表示到第 i i i件衣服洗完/晾幹所需的最小時間

顯然這兩個數組是單調不降的

我們需要兩者加起來最小的最大

是以可以通過排序不等式倒序和<亂序和<正序和

将兩個數組倒着相加取最大 就是最小的最大值

#include <bits/stdc++.h>
#define A 1000010

using namespace std;
typedef long long ll;
int l, n, m, a, b;
ll f1[A], f2[A];

int main(int argc, char const *argv[]) {
	cin >> l >> n >> m;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > q1, q2;
	for (int i = 1; i <= n; i++) cin >> a, q1.push(make_pair(a, a));
	for (int i = 1; i <= m; i++) cin >> b, q2.push(make_pair(b, b));
	for (int i = 1; i <= l; i++) {
		f1[i] = q1.top().first; int t = q1.top().second; q1.pop();
		q1.push(make_pair(f1[i] + t, t));
	}
	for (int i = 1; i <= l; i++) {
		f2[i] = q2.top().first; int t = q2.top().second; q2.pop();
		q2.push(make_pair(f2[i] + t, t));
	}
	ll ans = 0;
	for (int i = 1; i <= l; i++) ans = max(ans, 1LL * f1[i] + f2[l - i + 1]);
	cout << ans << endl;
}