当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

你现在要洗 l 件衣服。你有 n 台洗衣机和 m 台烘干机。由于你的机器非常的小,因此你每次只能洗涤(烘干)一件衣服。

i 台洗衣机洗一件衣服需要 w_i 分钟,第 i 台烘干机烘干一件衣服需要 d_i 分钟。

请问把所有衣服洗干净并烘干,最少需要多少时间?假设衣服在机器间转移不需要时间,并且洗完的衣服可以过一会再烘干。

l \leq 10 ^ 6, n, m \leq 10 ^ 5

如果没有洗衣 + 烘干这种鬼畜的限制,只考虑一个做的话是非常简单的,用一个堆维护贪心即可。假设我们已经求出了 a_i 表示洗完 i 件衣服需要的最小时间,b_i 表示烘干 i 件衣服需要的最小时间。

考虑到所有衣服都被烘干后烘干机全部是空的,可以把这个过程倒过来,这样子就和洗衣服一样了,如下图:

考虑这个东西随便排是没有关系的,设一个排列 p_1 , p_2 , p_3 , ... , p_l ,我们需要最小化

\max ( a_1 + b_{p_1} , a_2 + b_{p_2} , a_3 + b_{p_3} , ... , a_l + b_{p_l} )

这个「取最大值」+「加法」与「加法」+「乘法」操作是十分类似的,同样满足排序不等式,并且同样可以用数学归纳法证明。

回忆一下结论,顺序和大于等于乱序和大于等于逆序和,我们只需要令 p_i = n - i + 1 即可直接求出答案。

其他废话

注意不要像我一样读错题目。

代码

// =================================
//   author: memset0
//   date: 2019.07.22 18:31:19
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int i = (l), i##ed = (r); i <= i##ed; ++i)
#define for_each(i, a) for (size_t i = 0, i##ed = a.size(); i < i##ed; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
    x = 0; char c = getchar(); bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
    if (s != "") std::cout << s << ": ";
    for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 1e6 + 10;
ll ans, f[N], g[N];
int l, n, m, w[N], d[N];

struct info {
    ll time; int cost;
    inline bool operator<(const info &other) const {
        return time > other.time;
    }
};
std::priority_queue<info> W, D;

void main() {
    read(l), read(n), read(m);
    for (int i = 1; i <= n; i++) read(w[i]), W.push((info){w[i], w[i]});
    for (int i = 1; i <= m; i++) read(d[i]), D.push((info){d[i], d[i]});
    for (int i = 1; i <= l; i++) {
        auto it = W.top(); W.pop();
        f[i] = it.time, it.time += it.cost, W.push(it);
        it = D.top(); D.pop();
        g[i] = it.time, it.time += it.cost, D.push(it);
    }
    for (int i = 1; i <= l; i++)
        ans = std::max(ans, f[i] + g[l - i + 1]);
    print(ans, '\n');
}

} signed main() {
#ifdef memset0
    freopen("1.in", "r", stdin);
#endif
    return ringo::main(), 0;
}

参考资料

贪心 排序不等式 Favorite

已有 6 条评论

  1. hh hh

    fuck

  2. nibaba nibaba

    催更

  3. 你好,请教一个问题,您的old.memset0.cn用的是什么评论系统?

  4. Aiming_High Aiming_High

    太强啦!

Min_25 筛重新学习笔记
上一篇 «
LOJ6374 「SDWC2018 Day1」网格
» 下一篇