【题解】sdoj2796(同bzoj5088 hdu6000 雅礼集训2017Day4)(2018-08-11集训T3) 优先队列+贪心

题目描述

你现在要洗 l 件衣服。你有 n 台洗衣机和 m 台烘干机。由于你的机器非常的小，因此你每次只能洗涤（烘干）一件衣服。
第 i台洗衣机洗一件衣服需要 wi 分钟，第 i 台烘干机烘干一件衣服需要 di 分钟。
请问把所有衣服洗干净并烘干，最少需要多少时间？假设衣服在机器间转移不需要时间，并且洗完的衣服可以过一会再烘干。

输入

输入文件的第一行三个整数 l 、n 和 m
第二行 n 个整数 wi
第三行 m 个整数 di

输出

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

样例输入 1
1 1 1
1200
34

样例输入 2
2 3 2
100 10 1
10 10

样例输出 1
1234

样例输出 2
12

题解

用优先队列维护当前机器洗衣服的时间和洗衣结束的时间，每次去最小的结束时间加上洗衣所需时间加入队列。烘干时采用最大配最小的贪心策略。

代码

#include<cstdio>
#include<queue>
#include<algorithm>
#define _rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep_(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct node{
    ll wt,ed;//工作时间，结束时间 
    node(ll _wt,ll _ed):wt(_wt),ed(_ed){}
    bool operator <(const node&rhs)const{
    return ed>rhs.ed;}
};
priority_queue<node>w,d;
const int N=1e6+10;
int l,n,m;
ll ans=-INF;
ll end[N];
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&l,&n,&m);
    ll t;
    _rep(i,1,n)
    {
        scanf("%lld",&t);
        w.push(node(t,t));
    }
    _rep(i,1,m)
    {
        scanf("%lld",&t);
        d.push(node(t,t));
    }
    _rep(i,1,l)
    {
        node tmp=w.top();w.pop();
        end[i]=tmp.ed;
        tmp.ed+=tmp.wt;
        w.push(tmp);
    }
    rep_(i,l,1)
    {
        node tmp=d.top();d.pop();
        ans=max(ans,end[i]+tmp.ed);
        tmp.ed+=tmp.wt;
        d.push(tmp);
    }
    printf("%lld\n",ans);
    return 0;
}

光荣爆零Orz