前言
很久之前就把自己博客题解分区这个功能做出来了，但是一直没有去写题解。正好昨晚刚做出来一道比较简单的黑题，还热乎着，所以就写一写吧。
其实这是我的第二道黑题，也是第一道三分题，所以成为我的第一道题解还是很可以接受的。
不要害怕紫题黑题，实际上有可能只是思维难度高，实现起来比普及题还容易。而且如果你真的想在 OI 这条路上走远一点，迟早会做紫黑的。
题意
题目描述很清楚，因此直接复制洛谷上的了：
一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天 $(i=1,2,…,n)$ 需要 $r_i $ 块餐巾。餐厅可以在任意时刻购买新的餐巾，每块餐巾的费用为 $p$ 。使用过的旧餐巾，则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A，需要等待 $m_1$ 天后才能拿到新餐巾，其费用为 $c_1$ ；把一块旧餐巾送到清洗店B，需要等待 $m_2$ 天后才能拿到新餐巾，其费用为 $c_2$ 。例如，将一块第 $k$ 天使用过的餐巾送到清洗店A清洗，则可以在第 $k+m_1$ 天使用。
请为餐厅合理地安排好 $n$ 天中餐巾使用计划，使总的花费最小。
思路
其实这题原题是网络流，把天拆成早晚两个点然后进行连边，但是其实有更简单的贪心做法，并且在 $n$ 比较大的时候网络流还会被卡，所以这里只讲贪心。、
这里我们先假设 $m_1 \lt m_2$ 且 $c_1 \gt c_2$ ，即清洗店A快但贵，清洗店B慢但便宜，否则两者交换即可。我们形象地称呼前者为快洗，后者为慢洗。当然，这里还有一种特殊情况，就是慢洗比快洗贵，此时直接让 $m_2$ 等于 $m_1$ ，$c_2$ 等于 $c_1$，也就是相当于把慢洗换成快洗，这样就满足条件了。
首先一个注意到一个很显然的事实是，假设 $r_{1\to x}=r_1+r_2+\cdots+r_x$，即前缀和，那么我们需要购买的餐巾的数量的范围是 $[r_{1\to m_1},r_{1\to n}]$ 。因为就算是第一天开始快洗，我们也要到第 $m_1+1$ 天才能用，因此前面 $m_1$ 天需要的餐巾一定是靠买的；而当购买餐巾的费用比去慢洗还便宜的时候，自然是只买不洗的花费最小，此时 $n$ 天的餐巾全靠买。
尽管餐厅随时可以购买餐巾，但全部在最开始就买好一定是更优的，并且买来的越早用越好，因为提前买好提前用的话可能还可以靠洗来少买几条，或者换句话说就是餐巾利用率比较高。
这里我们转变一下视角，不是提前去洗好，而是换成当你餐巾不够用时，再从过去调度几块过来。（这应该算是一个比较常用的trick）
这样当我们已经决定好最开始买多少条餐巾时，可以发现后面 $n$ 天的贪心就很显然了：先用已经买好的，其次尽可能选择慢洗，最后再选择快洗。并且快洗尽可能选择较晚的餐巾，因为这样我们把较早的餐巾保留下来，过几天之后就可以用于慢洗。
这样看来，我们假设最开始买 $x$ 条餐巾，在确定的贪心方案下，最后的总费用应该也是确定并且与 $x$ 一一对应的，我们假设其为 $f(x)$ 。而我们一开始说过 $x$ 有范围，那么我们枚举 $x$ ，这题的答案应该就是 $\max f(x)$ 了。
本题到此，已经算是做出来了，接下来就是很经典的trick：范围内枚举，单次枚举不是 $O(1)$ ，这时候单调函数求零点就用二分，单峰函数求最值可以三分或者斜率二分，多峰函数求最值可以爬山或者模拟退火。
我们合理推测，如果一开始餐巾买少了，后面要么不够用，要么就得多洗几次快洗来弥补；如果一开始餐巾买多了，可以靠慢洗省下的费用都没省到。因此本题外层是一个单峰求最小值，我们进行一个三分或者斜率二分即可，本题结束。
代码
上面貌似讲了很多，但其实代码一点都不复杂，而且听起来时间复杂度很高，但实际上跑的飞快。check() 的时间复杂度是 $O(n(m_2-m_1))$ ，三分的时间复杂说法很多，所以这里就不算总复杂度了，能过，而且跑的飞快。
代码的部分有个小优化，做的时候很自然的想到的，就是对于所有能慢洗的餐巾，无论什么时候用的，哪怕你是远古时期用过的餐巾，都是等价的，所以我使用了一个变量 $f$ 直接来存可以慢洗的毛巾，这样就不需要枚举了，这也是为什么我比参考文献中那篇题解快，以及四倍经验里面拿到了三题的最优解。
另外这题看数据范围是需要开 long long 的，但实测不需要，估计是数据太水了。但尽管我觉得数据水，这个数据还是会卡掉大部分写的不好的网络流做法。
#include<cstdio>
#include<algorithm>
#define N 200005
#define INF 0x3f3f3f3f
using namespace std;
int n, m1, m2, c1, c2, p, r[N], res[N];
//res[i] 表示第 i 天使用过的毛巾的数量
inline int check(int num) {
int ans=num*p, f=0; //先买餐巾
for(register int i=1; i<=n; ++i) {
res[i] = 0; //使用前先清空
if(i > m2) f += res[i-m2]; //统计可以慢洗的餐巾
int need=r[i], k=min(need, num); //先用买好的
need-=k, num-=k, res[i]+=k;
if(!need) continue;
k = min(need, f); //慢洗
need-=k, f-=k, res[i]+=k, ans+=k*c2;
if(!need) continue;
for(register int j=i-m1; j&&j>i-m2; --j) { //快洗，越晚越好
k = min(need, res[j]);
need-=k, res[j]-=k, res[i]+=k, ans+=k*c1;
if(!need) break;
}
if(need) return INF; //餐巾不够用，刚开始买少了，直接返回INF即可
}
return ans;
}
int main() {
scanf("%d%d%d%d%d%d", &n, &m1, &m2, &c1, &c2, &p);
if(m1 > m2) swap(m1, m2), swap(c1, c2); //确保1为快洗，2为慢洗
if(c1 < c2) m2=m1, c2=c1;
int l=0, rr=0;
for(register int i=1; i<=n; ++i) scanf("%d", &r[i]), rr+=r[i];
for(register int i=1; i<=m1; ++i) l += r[i]; //l和rr是三分的范围
int ans = INF;
while(rr-l > 2) { //很普通的三分
int mid1=(l*2+rr)/3, mid2=(l+rr*2)/3;
int f1=check(mid1), f2=check(mid2);
if(f1 < f2) ans=min(ans, f1), rr=mid2-1;
else ans=min(ans, f2), l=mid1+1;
}
for(register int i=l; i<=rr; ++i) ans = min(ans, check(i));
printf("%d", ans);
return 0;
}
附录
原题链接
四倍经验，一道黑三道紫，数据范围还都比本题小很多，经验什么时候这么好赚了？而且除了 P1251 外剩下三题我都是最优解。
-
[USACO08NOV] Toys G - 洛谷（直接交就能AC）
-
餐巾计划问题 - 洛谷（注意读入顺序，只有这题需要开
long long） -
[HNOI2001] 软件开发 - 洛谷（注意读入顺序和题意小变动， $m_1,m_2$ 加一即可）
参考文献
版权信息
本文原载于reincarnatey.net，遵循CC BY-NC-SA 4.0协议，复制请保留原文出处。