ZCMU-2035 #6035. 「雅礼集训 2017 Day4」洗衣服 贪心+思路

链接点击打开链接

你现在要洗 l 件衣服。你有 n  台洗衣机和 m 台烘干机。由于你的机器非常的小，因此你每次只能洗涤（烘干）一件衣服。

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

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

Input

输入文件的第一行三个整数 l 、n 和 m。
第二行 n 个整数 w_i。
第三行 m 个整数 d_i 。

Output

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

Sample Input

1 1 1

1200

34

Sample Output

1234

HINT

对于 10% 10\% 10% 的数据，l=1 l = 1 l=1；

对于另外 20% 20\% 20% 的数据，l,n,m≤10 l, n, m \leq 10 l,n,m≤10；

对于另外 30% 30\% 30% 的数据，l≤1000,n,m≤100 l \leq 1000, n, m \leq 100 l≤1000,n,m≤100；

对于 100% 100\% 100% 的数据，l≤106,n,m≤105 l \leq 10 ^ 6, n, m \leq 10 ^ 5 l≤106,n,m≤105。

首先每件衣服洗好的时间很好算，用一个优先队列维护下一件衣服洗好的时间，每次弹出一个最短的时间。

关键是烘干的时间，我们假设T时刻所有的衣服都已经烘干了，那么之后的时间所有的烘干机全都是空着的，我们倒过来想烘干这件事情，其实就是跟洗衣是一样的，我们就可以把洗衣和烘干这两件事分开来考虑了。

在看下图，我们已经求出了3件衣服的洗衣时间和烘干时间，那么很显然最快的时间就是

max（ 洗衣时间+烘干时间 ）

最后一个问题就是哪件衣服用哪台烘干机

看下面一种情况，一看就是最慢的情况，需要2个最大相加。

所以我们应该让最快的洗衣时间和最慢烘干时间匹配，最慢的洗衣时间和最快烘干时间匹配。这样才能做到最快。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
LL N[maxn],M[maxn],L[1000005];
struct node{
   int id; LL t;
}y,yy;
bool operator<(node a,node b)
{
    return a.t>b.t;
}
int main()
{
    int l,n,m;
    scanf( "%d%d%d", &l, &n, &m );
    priority_queue<node>Q,P;
    for ( int i=1;i<=n;i++ ) scanf( "%lld", &N[i] );
    for ( int i=1;i<=m;i++ ) scanf( "%lld", &M[i] );
    for ( int i=1;i<=n;i++ )
        y.id=i, y.t=N[i], Q.push(y);
    for ( int i=1;i<=m;i++ )
        yy.id=i, yy.t=M[i], P.push(yy);
    for ( int i=1;i<=l;i++ )
    {
        int id=Q.top().id;
        LL t=Q.top().t; Q.pop();
        L[i]=t;
        y.id=id; y.t=t+N[id];
        Q.push(y);
    }
    LL ans = 0;
    for ( int i=l;i>0;i-- )
    {
        int id=P.top().id;
        LL tt=P.top().t; P.pop();
        yy.id=id;
        yy.t=tt+M[id];
        P.push(yy);
        ans = max( ans, L[i]+tt );
    }
    printf( "%lld\n", ans );
    return 0;
}