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;
}