洗衣服

LibreOJ-6035-洗衣服

分析

示意图：

实现

#include <iostream>
#include <queue>
using namespace std;

typedef long long LL;
const int N = 100010, M = 1000010;
struct node {
    int idx;
    LL t;
    bool operator < (const node& o) const {
        return t > o.t;
    }
};
int l, n, m;
int w[N], d[N];
LL t[M]; // t[i] 记录第 i 件衣服的作业完成时刻
priority_queue<node> pqw, pqd;

int main () {
    cin >> l >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> w[i];
    for (int i = 1; i <= m; ++ i) cin >> d[i];

    for (int i = 1; i <= n; ++ i) pqw.push({ i, w[i] });
    for (int i = 1; i <= m; ++ i) pqd.push({ i, d[i] });
    for (int i = 1; i <= l; ++ i) {
        node cur = pqw.top(); // 洗衣机
        pqw.pop();

        t[i] = cur.t;
        pqw.push({ cur.idx, cur.t + w[cur.idx] });
    }
    for (int i = l; i >= 1; -- i) {
        node cur = pqd.top(); // 烘干机
        pqd.pop();

        t[i] += cur.t;
        pqd.push({ cur.idx, cur.t + d[cur.idx] });
    }

    LL res = 0;
    for (int i = 1; i <= l; ++ i)
        res = max(res, t[i]);
    cout << res << endl;
    return 0;
}