Facebook Hacker Cup 2016 Round 1 Laundro, Matt

,

Laundro, Matt

問題

洗濯物が$L$個、洗濯機が$N$台、乾燥機が$M$台ある。 洗濯機はそれぞれ$W_i$分で1個洗濯でき、全ての乾燥機は$D$分で1個乾燥させられる。 洗濯物を全て洗濯し乾燥させるには最小で何分かかるか。

問題

simulation + 貪欲。

とりあえず全部の洗濯機を動かす。 早く終わった洗濯機に洗濯機を入れていたことにする。 乾燥は洗濯ができた順にする。

二分探索は不要。

実装

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct event_t { ll t; int i; };
bool operator < (event_t a, event_t b) { return a.t > b.t; } // reversed, preorder
ll solve() {
    ll l, n, m, d; cin >> l >> n >> m >> d;
    vector<ll> w(n); repeat (i,n) cin >> w[i];
    int unwashed = l;
    int undried = 0;
    int done = 0;
    int free_drier = m;
    priority_queue<event_t> q;
    repeat (i,n) q.push((event_t){ w[i], i });
    while (not q.empty()) {
        event_t e = q.top(); q.pop();
        if (e.i >= 0) { // washing done
            if (unwashed > 0) {
                -- unwashed;
                if (free_drier > 0) {
                    -- free_drier;
                    q.push((event_t){ e.t + d, -1 });
                } else {
                    ++ undried;
                }
            }
            if (unwashed > 0) {
                q.push((event_t){ e.t + w[e.i], e.i });
            }
        } else { // drying done
            ++ done;
            if (done == l) return e.t;
            if (undried > 0) {
                -- undried;
                q.push((event_t){ e.t + d, -1 });
            } else {
                ++ free_drier;
            }
        }
    }
    assert (false);
}
int main() {
    int testcases; cin >> testcases;
    repeat (testcase, testcases) {
        cout << "Case #" << testcase+1 << ": " << solve() << endl;
    }
    return 0;
}