Wash!!(HDU_6000)

2018-10-03 17:56:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

传送门:Wash!

题意:有n台洗衣机,m台烘干机,给出了每台机器处理意见衣服的时间,而且没见机器同时只能处理一件衣服。问如何选择机器才能使洗完衣服的时间最短。

思路:建两个优先队列,一个表示洗衣机,一个表示烘干机。每次取出最少工作时间的机器来进行洗衣,并将工作结束的时间加上处理一件衣服的时间。最后一件洗完的衣服对应着最长的结束时间,只有加上最短的烘干时间才能得到最短的结果。以此类推,倒数第二件衣服也是加上最短的烘干时间才可以得到最短时间。

贪心:前后的最长时间+最短时间得到的结果,要比从前往后最短的时间相加加到最后是最长的时间相加的结果短。

PS:注意数据范围的大小。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
typedef long long ll;
struct node
{
    ll x;//工作时间
    ll en;//工作到目前为止的结束时间
    friend bool operator<(node a,node b)
    {
        return a.en > b.en;
    }
} tmp;
priority_queue<node> wash;
priority_queue<node> dry;
int l,n,m;
ll a[maxn];

int main()
{
    int T,cnt = 1;
    scanf("%d",&T);
    while(T--)
    {
        while(!wash.empty()) wash.pop();
        while(!dry.empty())dry.pop();
        scanf("%d%d%d",&l,&n,&m);
        for(int i = 0; i<n; i++)
        {
            scanf("%lld",&tmp.x);
            tmp.en = tmp.x;
            wash.push(tmp);
        }
        for(int i = 0; i<m; i++)
        {
            scanf("%lld",&tmp.x);
            tmp.en = tmp.x;
            dry.push(tmp);
        }
        for(int i = 0; i<l; i++)
        {
            tmp = wash.top();//取出最短工作时间的机器来洗衣服
            a[i] = tmp.en;
            tmp.en += tmp.x;//结束时间加一段工作时间
            wash.pop();
            wash.push(tmp);//工作结束后投入等待序列
        }
        ll ans = 0;
        for(int i=l-1; i>=0; i--)
        {
            tmp = dry.top();
            ans = max(ans, a[i]+tmp.en);//更新洗衣服的结束时间
            tmp.en += tmp.x;
            dry.pop();
            dry.push(tmp);
        }
        printf("Case #%d: %lld\n",cnt++,ans);
    }
    return 0;
}
/*
样例输入:
2
1 1 1
1200
34
2 3 2
100 10 1
10 10
样例输出:
Case #1: 1234
Case #2: 12
*/
View Code

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:图像去模糊算法 循序渐进 附完整代码

下一篇:c++文件对齐