2018.10.27 loj#6035. 「雅禮集訓 2017 Day4」洗衣服（貪心+堆）

傳送門

顯然的貪心題啊。。。考試沒調出來10pts滾了妙的一啊

直接分别用堆貪心出洗完第 i i i件衣服需要的最少時間和晾完第 i i i件衣服需要的最少時間。

我們設第一個算出來的數組是 a a a，第二個是 b b b，然後令 c c c數組是 b b b的一個任意排列。

于是要求 m i n min min{ m a x max max{ a 1 + c 1 , a 2 + c 2 , . . . a l + c l a_1+c_1,a_2+c_2,...a_l+c_l a1​+c1​,a2​+c2​,...al​+cl​}}

裡面東西跟排序不等式很像啊 ，于是 a a a正序 b b b倒序加起來取最大值就行了。

代碼：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=1e6+5;
int L,n,m;
typedef long long ll;
ll a[N],b[N],t1[N],t2[N],ans=0;
int main(){
	L=read(),n=read(),m=read();
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q1,q2;
	for(int i=1,v;i<=n;++i)q1.push(make_pair(v=read(),v));
	for(int i=1,v;i<=m;++i)q2.push(make_pair(v=read(),v));
	for(int i=1;i<=L;++i){
		pair<ll,ll>tmp=q1.top();
		q1.pop();
		t1[i]=tmp.first,tmp.first+=tmp.second,q1.push(tmp);
		tmp=q2.top();
		q2.pop();
		t2[i]=tmp.first,tmp.first+=tmp.second,q2.push(tmp);
	}
	for(int i=1;i<=L;++i)ans=max(ans,t1[i]+t2[L-i+1]);
	cout<<ans;
	return 0;
}