CCPC-final 2016 B - wash

题意

L件衣服，N个洗衣机，M个烘干机。每个洗衣机和烘干机都有自己工作所需的时间，问洗完并烘干玩所有衣服的最短时间。

思路

很容易想到用优先队列获取没件衣服的最短时间，然后用同样的方法求得烘干的时间。

将两边的时间反向加起来，取最大值就是答案。

#include <bits/stdc++.h> 
using namespace std;

const int maxn = ;

long long T[maxn];
struct node
{
    long long base, next;
    node(){}
    node(long long base, long long next):base(base),next(next){}
    bool operator<(const node &b) const
    {
        return next > b.next;
    }
};

int main()
{
    int t;
    scanf("%d", &t);
    for (int cas = ; cas <= t; cas++)
    {
        int l, n, m;
        scanf("%d %d %d", &l, &n, &m);
        priority_queue<node>q;
        for (int i = ; i < n; ++i)
        {
            int w;
            scanf("%lld", &w);
            q.push(node(w, w));
        }
        for (int i = ; i < l; i++)
        {
            node now = q.top();
            q.pop();
            T[i] = now.next;
            q.push(node(now.base, now.next + now.base));
        }
        while (!q.empty())
            q.pop();
        for (int i = ; i < m; i++)
        {
            int d;
            scanf("%lld", &d);
            q.push(node(d, d));
        }
        long long ans = ;
        for (int i = l - ; i >= ; i--)
        {
            node now = q.top();
            q.pop();
            ans = max(ans, now.next + T[i]);
            q.push(node(now.base, now.next + now.base));
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
}