多倍经验
题目思路
约定 $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。
丑陋代码
#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;
}