ACM模版

描述

题解

给定 L 件衣服让你去洗，洗衣房有 n 个洗衣机和 m 个烘***，每个设备都给定你完成工作所需时间，但是由于设备比较烂，每个设备在某一段时间内只能洗一件衣服，问洗完这 L 件衣服最短用时多久？

这个题很简单，想要时间最短，自然是考虑烘干最后一件衣服所需的时间，那么怎么要这个最后一件衣服在最短时间内处理完呢？这里就涉及到贪心了，首先我们可以根据洗衣机洗涤时间处理出来每件衣服洗干净的最早时间，然后呢，将最晚洗干净的衣服放进目前烘干这件衣服最早的烘***，以此类推，这里很容易想到的是维护两个优先队列即可。

强调一点，在这里每台机器的完成工作所需的时间并不是贪心的决定性条件，因为考虑到机器的复用，所以我们需要根据最早完成这件工作的时间来贪心。洗涤和烘干两个过程都是如此贪心，不过为了时间最短，我们需要用洗涤最早和烘干最晚的搭配，用洗涤最晚和烘干最早的搭配……这样就能保证最后一件衣服用时最短。至于哪一件是最后烘干完成的，取最值即可。

代码

#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int L, n, m;
ll cost[MAXN];

struct node
{
    ll cost, base;

    bool operator < (const node &rhs) const
    {
        return cost > rhs.cost;
    }
};

ll x;
priority_queue<node> pqn1, pqn2;

int main()
{
    int T;
    scanf("%d", &T);

    for (int ce = 1; ce <= T; ce++)
    {
        while (!pqn1.empty())
        {
            pqn1.pop();
        }
        while (!pqn2.empty())
        {
            pqn2.pop();
        }

        scanf("%d%d%d", &L, &n, &m);
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &x);
            pqn1.push({x, x});
        }
        for (int i = 0; i < m; i++)
        {
            scanf("%lld", &x);
            pqn2.push({x, x});
        }

        node t;
        for (int i = 0; i < L; ++i)
        {
            t = pqn1.top();
            pqn1.pop();
            cost[i] = t.cost;
            t.cost += t.base;
            pqn1.push(t);
        }

        ll ans = 0;
        for (int i = L - 1; i >= 0; i--)
        {
            t = pqn2.top();
            pqn2.pop();
            ans = max(ans, t.cost + cost[i]);
            t.cost += t.base;
            pqn2.push(t);
        }

        printf("Case #%d: %lld\n", ce, ans);
    }

    return 0;
}