upc 6910: 洗衣服（优先队列+贪心）

6910: 洗衣服

时间限制: 2 Sec  内存限制: 128 MB
提交: 26  解决: 7
[提交] [状态] [讨论版] [命题人:admin]

 

题目描述

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

输入

输入第一行有3个整数L,n和m。第二行有n个整数w1,w2,...,wn。第三行有m个整数d1,d2,...,dm。

输出

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

样例输入

1 1 1
1200
34

样例输出

1234

提示

 

来源/分类

中山纪念中学20170310 

[提交] [状态]

【总结】

好题，好神仙题，好神仙贪心题。

【分析】

按照贪心策略，把每一个洗衣机都压入优先队列，压入的权值代表：如果我要用这个洗衣机，最早将在什么时刻洗完一件衣服。

很明显，如果我用某个洗衣机洗过一次，那么其他衣服想用它的话，需要总共w[i]*2的时间洗完。

 

烘干的话，我们想要最晚烘干的那件衣服尽量早，所以我们让最晚洗完的那件衣服，先烘干（不要等了，这最晚洗完的要是等，肯定会拖延总时间）

以此贪心，解题。。

【代码】

/****
***author: winter2121
****/
#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define SI(i) scanf("%d",&i)
#define PI(i) printf("%d\n",i)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int MAX=2e5+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int dir[9][2]={0,1,0,-1,1,0,-1,0, -1,-1,-1,1,1,-1,1,1};
template<class T>bool gmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>bool gmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>void gmod(T &a,T b){a=(a%mod+b)%mod;}

typedef pair<ll,int>PII;
priority_queue<PII,vector<PII>,greater<PII> >q1,q2;

int L,n,m;
ll tim[MAX*5],w[MAX],d[MAX];
int main()
{
    scanf("%d%d%d",&L,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
        q1.push(PII(w[i],i)); //装一个洗衣机，表示用了这个洗衣机，等待w[i]时间会洗完
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&d[i]);
        q2.push(PII(d[i],i)); //装一个烘干机，同上
    }
    for(int i=0;i<L;i++)//洗衣服
    {
        PII u=q1.top(); q1.pop();
        tim[i]=u.first; //最快洗完这个衣服的时间
        u.first+=w[u.second];
        q1.push(u);
    }
    ll ans=0;
    for(int i=L-1;i>=0;i--) //让最晚洗完的衣服，尽早的烘干，才能保证最长的那个时间尽量短
    {
        PII u=q2.top(); q2.pop();
        tim[i]+=u.first;
        u.first+=d[u.second];
        q2.push(u);
        ans=max(ans,tim[i]); //取一个花费时间最长的
    }
    printf("%lld\n",ans);
    return 0;
}