洗衣服(优先队列+贪心)

                                                 洗衣服

                                                                 时间限制: 2 Sec  内存限制: 128 MB
                                                                                提交: 51  解决: 14
                                                                 [提交] [状态] [讨论版] [命题人: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

                                                                 [提交]           [状态]

题解

这道题属于一眼看上去就很简单但是仔细想又不是特别好想的题  要求的是最小时间 基本上都能想到贪心 用优先队列处理  比较难想到的是洗完衣服之后烘干的过程  所以我们应该让最快的洗衣时间和最慢烘干时间匹配，最慢的洗衣时间和最快烘干时间匹配。这样才能做到最快 每一次出队列的元素需要再加上他当前所消耗的时间再次入队列（等待需要的时间就是当前所消耗的时间）

pair的用法

#include<bits/stdc++.h>
#define ll long long
const int maxn=1e5+5;
using namespace std;
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
ll qpow(ll x, ll y, ll mod){ll s=1;while(y){if(y&1)s=s*x%mod;x=x*x%mod;y>>=1;}return s;}
ll l,n,m;
ll w[maxn],d[maxn];
ll t[1000005];//记录每件衣服洗完+烘干的时间

typedef pair<ll,ll> P;//first 表示编号 second 表示时间
priority_queue<P,vector<P>,greater<P> >x,h;
int main()
{

    scanf("%lld%lld%lld",&l,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
        x.push(make_pair(w[i],i));

    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&d[i]);
        h.push(make_pair(d[i],i));
    }
    for(int i=1;i<=l;i++)
    {
        P q=x.top();
        x.pop();
        t[i]=q.first;
        ll b=q.second;
        x.push(make_pair(q.first+w[b],b));

    }
    ll ans=0;
    for(int i=l;i>0;i--)
    {
        P q=h.top();
        h.pop();
        t[i]+=q.first;
        ll b=q.second;
        h.push(make_pair(q.first+d[b],b));
        ans=max(ans,t[i]);
    }
    printf("%lld\n",ans);

    return 0;
}

普通的结构体

#include<bits/stdc++.h>
#define ll long long
const int maxn=1e5+5;
using namespace std;
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
ll qpow(ll x, ll y, ll mod){ll s=1;while(y){if(y&1)s=s*x%mod;x=x*x%mod;y>>=1;}return s;}
ll l,n,m;
ll w[maxn],d[maxn];
ll t[1000005];//记录每件衣服洗完+烘干的时间
struct node
{
    ll id;
    ll t;
}u,v;
bool operator<(node a,node b)
{
    return a.t>b.t;
}
priority_queue<node>x,h;
int main()
{

    scanf("%lld%lld%lld",&l,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
        u.id=i;
        u.t=w[i];
        x.push(u);

    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&d[i]);
         v.id=i;
         v.t=d[i];
         h.push(v);
    }
    for(int i=1;i<=l;i++)
    {
        node q=x.top();
        x.pop();
        t[i]=q.t;
        ll b=q.id;
        u.t=q.t+w[b];
        u.id=q.id;
        x.push(u);

    }
    ll ans=0;
    for(int i=l;i>0;i--)
    {
        node q=h.top();
        h.pop();
        t[i]+=q.t;
        ll b=q.id;
        v.t=q.t+d[b];
        v.id=q.id;
        h.push(v);
        ans=max(ans,t[i]);
    }
    printf("%lld\n",ans);

    return 0;
}