JZOJ 5009. 【NOI2017模拟3.10】洗衣服（堆）

JZOJ 5009. 【NOI2017模拟3.10】洗衣服

题目

Description

你现在要洗L件衣服。你有n台洗衣机和m台烘干机。由于你的机器非常的小，因此你

每次只能洗涤(烘干) 一件衣服。

第i台洗衣机洗一件衣服需要wi 分钟，第i台烘干机烘干一件衣服需要di 分钟。

请问把所有衣服洗干净并烘干，最少需要多少时间？假设衣服在机器间转移不需要时间，并且洗完的衣服可以过一会再烘干。

Input

输入文件的第一行有3 个整数L, n 和m 。

第二行有n 个整数w1,w2, . . . , wn 。

第三行有m 个整数d1, d2, . . . , dm 。

Output

输出一行一个整数，表示所需的最少时间。

Sample Input

输入1：

1 1 1

1200

34

输入2：

2 3 2

100 10 1

10 10

Sample Output

输出1：

1234

输出2：

12

Data Constraint

题解

• 可以把洗衣服和烘干看作是两个互不相干的过程，先计算出第 i i i件衣服洗的时间 s 1 [ i ] s1[i] s1[i]，第 i i i件衣服烘干的时间 s 2 [ i ] s2[i] s2[i]，分别排序后 a n s = m a x ( s 1 [ i ] , s 2 [ n − i + 1 ] ) ans=max(s1[i],s2[n-i+1]) ans=max(s1[i],s2[n−i+1])，也就是最大和最小的对应匹配，这样可以使总时长尽可能的小。
• 考虑怎么分别计算洗衣服和烘干的时间？
• 其实非常简单，用堆维护，第 i i i次在堆中取出最小值，作为当前的 s 1 [ i ] / s 2 [ i ] s1[i]/s2[i] s1[i]/s2[i]，然后再把取出的数再加上一次的时间放回堆中。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
#define ll long long
ll a[N],s1[N*10],s2[N*10];
int s;
struct node
{
	int x;
	ll t;
}f[N];
void up(int k)
{
	while(k>1&&f[k/2].t>f[k].t) 
	{
		swap(f[k],f[k/2]);
		k/=2;
	}
}
void down(int k)
{
	while((k*2<=s&&f[k].t>f[k*2].t)||(k*2<s&&f[k].t>f[k*2+1].t))
	{
		int l=k*2;
		if(k*2<s&&f[k*2+1].t<f[k*2].t) l++;
		swap(f[k],f[l]);
		k=l;
	}
}
int main()
{
	int L,n,m,i;
	scanf("%d%d%d",&L,&n,&m);
	for(i=1;i<=n;i++) scanf("%lld",&a[i]);
	s=0;
	for(i=1;i<=n;i++)
	{
		f[++s].x=i,f[s].t=a[i];
		up(s);
	}
	for(i=1;i<=L;i++)
	{
		node t=f[1];
		s1[i]=t.t;
		f[1]=f[s];
		s--;
		down(1);
		f[++s].t=t.t+a[t.x],f[s].x=t.x;
		up(s);
	}
	for(i=1;i<=m;i++) scanf("%lld",&a[i]);
	s=0;
	for(i=1;i<=m;i++)
	{
		f[++s].x=i,f[s].t=a[i];
		up(s);
	}
	for(i=1;i<=L;i++)
	{
		node t=f[1];
		s2[i]=t.t;
		f[1]=f[s];
		s--;
		down(1);
		f[++s].t=t.t+a[t.x],f[s].x=t.x;
		up(s);
	}
	sort(s1+1,s1+L+1);
	sort(s2+1,s2+L+1);
	ll ans=0;
	for(i=1;i<=L;i++) ans=max(ans,s1[i]+s2[L-i+1]);
	printf("%lld",ans);
	return 0;
}