loj6035「雅礼集训 2017 Day4」洗衣服

题目

「雅礼集训 2017 Day4」洗衣服

题解

先单独考虑洗和烘干，问题简化为一个非常简单的贪心：每次选择处理完这件衣服总耗时最短的机器，可以堆维护

再考虑将其结合。衣服需要先洗再烘，所以烘干所有衣服的时刻必然在洗完衣服的时刻之后

aw[i], ad[i] 分别记录洗完，烘干i件衣服的耗时

t取max就可以了

注意long long

代码

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define ll long long

inline ll read()
{
	ll x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}

int l, n, m;
ll aw[N], ad[N];

struct node
{
	ll used, x;
	friend bool operator < (node a, node b)
	{
		return a.used + a.x > b.used + b.x;
	}
}w[N], d[N];

priority_queue<node> qw, qd;

int main()
{
	l = read(); n = read(); m = read();
	for(int i = 1; i <= n; i++) w[i].x = read(), qw.push(w[i]);
	for(int i = 1; i <= m; i++) d[i].x = read(), qd.push(d[i]);
	for(int i = 1; i <= l; i++)
	{
		node k = qw.top(); qw.pop();
		k.used += k.x; qw.push(k);
		aw[i] = k.used;
		
		k = qd.top(); qd.pop();
		k.used += k.x; qd.push(k);
		ad[i] = k.used;
	}
	ll ans = 0;
	for(int i = 1; i <= l; i++) ans = max(ans, aw[i] + ad[l - i + 1]);
	cout << ans;
	return 0;
}