Company¶
题意¶
在第 i 天会有 mi 名员工上班，公司每天都要为每位上班的员工发一条消毒毛巾。一条消毒毛巾在使用后，可以选择花费 a 天 fa 元消毒，也可以花费 b 天 fb 元消毒。购买新的消毒毛巾要花费 f 元。求公司最少要花费多少钱。
解析¶
这道题是费用流经典问题 餐巾计划 的加强版，n 扩大到了 105。那么我们就不能使用费用流了。
假设我们已经确定了购买毛巾的数量 x。维护三个双端队列 qb,qa,qf，每次使用完毛巾后就将其推入 qf，表示距使用完不足 a 天的所有毛巾；若 qf 的队首距使用完达到 a 天，则推入 qa；若 qa 的队首距使用完达到 b 天，则推入 qb。若当前可用毛巾数量不足 mi，则优先从 qb 中获取没洗的毛巾，每件代价为 fb；否则从 qa 的尾部获取没洗的毛巾，每件代价为 fa。
于是对于确定的 x，我们能够在 O(n) 的时间复杂度内计算答案了。感性理解，答案关于 x 是凸的，可以三分取最优值。
实现¶
#include <bits/stdc++.h>
const int maxn = 1e5 + 19;
int n, a, b, f, fa, fb, m[maxn];
int check(int x){
int res = x * f, now = x;
std::deque<std::pair<int, int> > qb, qa, qf;
for(int i = 1; i <= n; ++i){
while(!qf.empty() && qf.front().first + a + 1 <= i)
qa.push_back(qf.front()), qf.pop_front();
while(!qa.empty() && qa.front().first + b + 1 <= i)
qb.push_back(qa.front()), qa.pop_front();
while(now < m[i]){
if(!qb.empty()){
int d = std::min(qb.front().second, m[i] - now);
qb.front().second -= d, now += d, res += d * fb;
if(!qb.front().second) qb.pop_front();
}
else if(!qa.empty()){
int d = std::min(qa.back().second, m[i] - now);
qa.back().second -= d, now += d, res += d * fa;
if(!qa.back().second) qa.pop_back();
}
else return 1e9;
}
now -= m[i], qf.push_back(std::make_pair(i, m[i]));
}
return res;
}
int main(){
std::scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &fa, &fb);
int l = 0, r = 0;
for(int i = 1; i <= n; ++i)
std::scanf("%d", m + i), l = std::max(l, m[i]), r += m[i];
while(r - l > 6){
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if(check(m1) < check(m2)) r = m2;
else l = m1;
}
int ans = 1e9;
for(int i = l; i <= r; ++i) ans = std::min(ans, check(i));
std::printf("%d\n", ans);
return 0;
}