题意:L堆衣服,N台洗衣机,M台脱水机,给出每台机器的每次工作的时间 Wi,Di。一台机器一次只能给一堆衣服工作,求洗完衣服最少需要多少时间。
分析:2016 ccpc/final的一个题,这个贪心这是好难想到啊。看了这篇题解:见这里,思想就是最小洗完时间加最大脱水时间取大,仔细想想这个贪心确实是正确的啊,虽然我不能证明它,但是直观感觉这样得到的答案确实是最优的。然后就按照这个思想贪心做就好了。

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint()
    {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
const int maxn = 1000010;
long long w[maxn], d[maxn];
long long maxx[maxn];
struct node{
    long long tim;
    int id;
    node(){}
    node(long long tim, int id) : tim(tim), id(id) {}
    bool operator <(const node &rhs) const{
        return tim > rhs.tim;
    }
};
int main()
{
    int ks = 0;
    int T, L, N, M;
    //scanf("%d", &T);
    T = io.xint();
    while(T--)
    {
        //memset(maxx, 0, sizeof(maxx));
        //scanf("%d%d%d", &L, &N, &M);
        L = io.xint(), N = io.xint(), M = io.xint();
        for(int i = 1; i <= N; i++) w[i] = io.xint();
        for(int i = 1; i <= M; i++) d[i] = io.xint();
        long long ans = -1;
        priority_queue <node> q1, q2;
        for(int i = 1; i <= N; i++){
            q1.push(node(w[i], i));
        }
        for(int i = 1; i <= M; i++){
            q2.push(node(d[i], i));
        }
        for(int i = 1; i <= L; i++){
            node cur = q1.top();
            q1.pop();
            long long nex_time = cur.tim;
            long long cur_time = cur.tim + w[cur.id];
            node nex;
            nex.tim = cur_time;
            nex.id = cur.id;
            q1.push(nex);
            maxx[i] = nex_time;
        }
        for(int i = L; i >= 1; i--){
            node cur = q2.top();
            q2.pop();
            long long nex_time = cur.tim;
            long long cur_time = cur.tim + d[cur.id];
            node nex;
            nex.tim = cur_time;
            nex.id = cur.id;
            q2.push(nex);
            ans = max(ans, nex_time + maxx[i]);
        }
        printf("Case #%d: %I64d\n", ++ks, ans);
    }
    return 0;
}