多倍经验

题目思路

约定 $p$ 为干净餐巾价格，$m_1,m_2$ 为快洗慢洗所需要的天数，$c_1,c_2$ 为快洗慢洗一个的代价，$m_1\leq m_2,c_1\geq c_2$，不满足的话自己 swap 一下即可。

一个显然的性质是我们可以把要用的餐巾一次性买好。考虑如果我们知道了具体要买多少餐巾。设要买 $x$ 条，$f(x)$ 表示买了 $x$ 条餐巾最后的总花费。如果不够用为 $+\infty$。手玩几个找找规律~~或者是靠小学数学题告诉你的经验~~可以发现这是个单谷函数，有一个极点。显然我们要找出这个极点并且求出对应的函数值。

单谷函数，显然是需要三分的。那么这个 $f(x)$ 到底应该怎么算呢？

先思考，每天可以用的餐巾从哪里来？

买来的新的没用完。
快洗洗完的。
慢洗洗完的。

之后会发现优先使用新的餐巾会更优，这个是先用的。

然后在可以的情况下优先使用较晚慢洗好的。慢洗全用完之后用较晚快洗好的。

优先使用较晚得到的餐巾，可以尝试让更早的餐巾去慢洗，最小化代价。

优先用慢洗可以尽量减少消费，和上面一个道理，可能能让快洗的餐巾去慢洗。

这时很显然这就是贪心的过程，~~因为这题是洛谷秋令营提高组贪心课后作业。~~

注意到我们需要从头放，从尾巴取，所以我们实现的时候可以使用双端队列模拟这一贪心过程，即使用 C++ 的 STL 容器 deque。

丑陋代码

Luogu record 128374675

#include <bits/stdc++.h>
using namespace std;
#define upd1(a, b, c)                            \
    while (!a.empty() && a.front().day <= i - c) \
    {                                            \
        b.push_back(a.front());                  \
        a.pop_front();                           \
    }
#define upd2(a, b)                   \
    while (cnt > 0 && !a.empty())    \
    {                                \
        mn = min(cnt, a.back().cnt); \
        ret += mn * b;               \
        cnt -= mn;                   \
        if (!(a.back().cnt -= mn))   \
            a.pop_back();            \
    }
struct info
{
    int day, cnt;
};
int n, m1, m2, c1, c2, p;
deque<info> buy;
deque<info> fst;
deque<info> slw;
int a[200020];
int f(int k)
{
    buy.clear();
    fst.clear();
    slw.clear();
    int ret = k * p;
    for (int i = 1; i <= n; i++)
    {
        upd1(buy, fst, m1);
        upd1(fst, slw, m2);
        int cnt = a[i];
        int mn = min(cnt, k);
        cnt -= mn;
        k -= mn;
        upd2(slw, c2);
        upd2(fst, c1);
        if (cnt > 0)
            return INT_MAX;
        buy.push_back({i, a[i]});
    }
    return ret;
}
int main()
{
    cin >> n >> m1 >> m2 >> c1 >> c2 >> p;
    if (m1 > m2)
        swap(m1, m2), swap(c1, c2);
    if (c1 < c2)
        m2 = m1, c2 = c1;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 0, r = accumulate(a + 1, a + n + 1, 0);
    while (l <= r)
    {
        int ml = l + (r - l) / 3;
        int mr = r - (r - l) / 3;
        int vl = f(ml), vr = f(mr);
        if (vl >= vr)
            l = ml + 1;
        else
            r = mr - 1;
    }
    cout << min(f(l), f(r)) << endl;
    return 0;
}

P4480 [BJWC2018] 餐巾计划问题题解