D 天, 第 i 天需要 ti 个物品. 购买一个物品花费 c 元, 消毒后才能再次使用. 两种消毒方式: 收取 c1 元, n1 天后可以再次使用; 收取 c2 元, n2 天后可以再次使用. 储存是免费的, 且不会弄脏物品. 求最小花费. (1 ≤ n1,n2 ≤ D, 1 ≤ c1,c2,c ≤ 60, 1 ≤ ti ≤ 50, 1 ≤ D ≤ 10^5) 餐巾计划问题的数据加强版.
如果购买的物品过少, 不存在合法方案, 视花费为正无穷. 那么, 最小花费是关于购买物品个数的单峰函数. 网上说, 因为可以费用流, 流量等于玩具数, 所以是单峰的. 不太对啊......通常是这样建图的, 流量 = 购买的物品数 + 清洗的物品数. 幸运的是, 的确可以建出流量 = 清洗的物品数的网络, 见我以前的题解. 读自己以前的文字, 感觉现在语文能力有所下降......
已知购买的物品个数, 可以贪心求出最小花费.
设 n1 > n2, c1 < c2. 如果 c1 > c2, 则令 c1 = c2.
首先, 可以把购买操作全部放到最前面; 如果某个物品是购买得到的, 前面有个物品是清洗得到的, 交换它们的位置, 不会产生影响.
购买的机会用完之后, 只有两种选择: 慢洗 (即 n1,c1), 或快洗 (n2,c2). 能用慢洗就用慢洗. 只能用快洗, 优先选择时间最近的. 这两条法则也可以通过交换的方式来说明.
用队列维护即可.
为什么不能直接贪心呢? 等待一段时间, 清洗的代价可能减少. 如:
D=3 (n1,c1)=(2,1) (n2,c2)=(1,3) c=4
t={1,1,1}4+3+3=10. 第二天放弃快洗, 转而购买新的, 答案为4+4+1=9.
一开始没有意识到快洗得优先选择时间最近的......
const int D = 1e5, inf = 1e9;
int d, n1, n2, c1, c2, c, t[D], v[D], Q[D];
int calc(int x)
{
int cost = x * c, * p = Q, * q = Q-1;
rep (i, 0, d)
{
if (i >= n2) *++q = i-n2;
int u = min(x, t[i]), tmp = t[i] - u;
x -= u;
while (tmp && q-p >= 0 && i-*p >= n1)
{
u = min(v[*p], tmp);
tmp -= u, v[*p] -= u, cost += u * c1;
p += !v[*p];
}
while (tmp && q-p >= 0)
{
u = min(v[*q], tmp);
tmp -= u, v[*q] -= u, cost += u * c2;
q -= !v[*q];
}
if (tmp) return inf;
v[i] = t[i];
}
return cost;
}
int main()
{
int l = 1, r = 0;
scanf("%d%d%d%d%d%d", &d, &n1, &n2, &c1, &c2, &c);
rep (i, 0, d) scanf("%d", t+i), r += t[i];
if (n2 > n1) swap(n1, n2), swap(c1, c2);
if (c1 > c2) c1 = c2;
if (c1 >= c || l == r) return printf("%d\n", r*c), 0;
while (r-l > 1)
{
int m1 = (l+l+r)/3, m2 = (l+r+r)/3;
if (calc(m1) >= calc(m2)) l = m1+1;
else r = m2-1;
}
printf("%d\n", min(calc(l), calc(r)));
return 0;
}