Hdu6000 wash (priority queue + greed)

Problem Description

Mr.Panda is about to engage in his favourite activity doing laundry!
He's brought L indistinguishable loads of laundry to his local
laundromat, which has N washing machines and M dryers.The ith washing
machine takes Wi minutes to wash one load of laundry, and the ith
dryer takes Di minutes to dry a load of laundry. At any point in time,
each machine may only be processing at most one load of laundry. As
one might expect, Panda wants to wash and then dry each of his L loads
of laundry. Each load of laundry will go through the following steps
in order:
1. A non-negative amount of time after Panda arrives at the laundromat, Panda places the load in an unoccupied washing machine i.
2. Wi minutes later, he removes the load from the washing machine, placing it in a temporary holding basket (which has unlimited space)
3. A non-negative amount of time later, he places the load in an unoccupied dryer j
4. Dj minutes later, he removes the load from the dryer Panda can instantaneously add laundry to or remove laundry from a machine. Help
Panda minimize the amount of time (in minutes after he arrives at the
laundromat) after which he can be done washing and drying all L loads
of laundry!

Input

The first line of the input gives the number of test cases, T. T test
cases follow. Each test case consists of three lines. The first line
contains three integer L, N, and M. The second line contains N
integers W1,W2,...,WN representing the wash time of each wash machine.
The third line contains M integers D1,D2,...,DM representing the dry
time of each dryer.

Output

For each test case, output one line containing "Case #x: y", where x
is the test case number (starting from 1) and y is the minimum time it
will take Panda to finish his laundry. limits

∙1≤T≤100. ∙1≤L≤106. ∙1≤N,M≤105. ∙1≤Wi,Di≤109.

Sample Input

2
1 1 1
1200
34
2 3 2
100 10 1
10 10

Sample Output

Case #1: 1234
Case #2: 12

thinking

First of all, I want to go to the laundry.
This man has L clothes. The laundry room has n washing machines and m dryers. First, the first line of the title gives the three numbers, and then there are two lines. The first line each number WiWi represents the washing time of the i-th washing machine w, and then the first line each number DiDi represents the drying time of the i-th dryer.

We can use a priority queue to maintain the washing time of the washing machine, and let the first out team spend less time. The minimum washing time t[i] of each garment is processed first. After a certain garment is processed late, the time of washing this garment is added when entering the team (see the implementation process for details)

When we deal with t[i], the problem we are facing now is drying. As we do when washing clothes, drying also uses priority queue, small first out team. Then our greedy strategy is to let the last washed clothes use the washing machine with the least drying time when drying, so that the maximum value of washing + drying clothes is the answer. Large data, long long is needed

Code

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long ll;
const ll N=1e6+20;
struct node
{
    ll x,val;//Time and current time for laundry
    node() {}
    node(ll _x,ll _val)
    {
        x=_x;
        val=_val;
    }
    bool friend operator < (node a,node b)
    {
        return a.val>b.val;//Make the time-consuming first out team
    }
} a[N];
ll t[N],L,n,m;//t[i] represents the earliest washing time of the ith garment
int main()
{
    ll T,x,kase=1;
    scanf("%lld",&T);
    while(T--)
    {
        priority_queue<node>q;
        scanf("%lld%lld%lld",&L,&n,&m);
        for(ll i=0; i<n; i++)
        {
            scanf("%lld",&x);
            q.push(node(x,x));
        }
        for(ll i=0; i<L; i++)
        {
            node now=q.top();
            q.pop();
            t[i]=now.val;//Find out the earliest washing time of the ith garment
            q.push(node(now.x,now.x+now.val));//Count in the washing time of this dress
        }
        while(!q.empty())q.pop();//Clear queue
        for(ll i=0; i<m; i++)
        {
            scanf("%lld",&x);
            q.push(node(x,x));
        }
        ll ans=0;
        for(ll i=L-1; i>=0; i--)
        {
            node now=q.top();
            q.pop();
            ans=max(ans,t[i]+now.val);//Washing time + drying time
            q.push(node(now.x,now.x+now.val));
        }
        printf("Case #%lld: %lld\n",kase++,ans);
    }
    return 0;
}

Tags: less

Posted on Tue, 31 Mar 2020 16:27:11 -0700 by kazil