CF893D: Credit Card

只在检查日充钱;维护余额可达区间,区间全负时强制充一次,否则抬高下界,得到最少充钱次数。

来源 Codeforces 893 D · 难度 Codeforces 1900 · 时间 2 s,空间 256 MB · 标签 贪心 / 模拟 / 区间 / 可行性

题目描述

有 𝑛 天,账户初始余额为 0,余额上限为 𝑑。第 𝑖 天晚上发生交易 𝑎𝑖:

  • 若 𝑎𝑖>0,账户增加 𝑎𝑖;
  • 若 𝑎𝑖<0,账户减少 −𝑎𝑖;
  • 若 𝑎𝑖=0,检查余额,要求余额非负。

每个早晨可以存入任意正整数,但任意时刻余额都不能超过 𝑑。求最少需要在多少个早晨存款;无解输出 −1。

1≤𝑛≤105,1≤𝑑≤109,−104≤𝑎𝑖≤104。

题解

存款只会抬高余额,因此不需要在非检查日存款:若某次存款发生在非检查日,把它推迟到下一次检查日,不会减少可行性,也不会增加次数。于是只需考虑 𝑎𝑖=0 的检查日。

维护当前所有可达余额的区间 [𝐿,𝑅],其中 𝐿 是最小可达余额,𝑅 是最大可达余额;区间内的整数都可达,且当前存款次数不变。

初始时 𝐿=𝑅=0。

  • 若 𝑎𝑖≠0,令 𝐿←𝐿+𝑎𝑖,𝑅←𝑅+𝑎𝑖。

    • 若 𝐿>𝑑,无解。
    • 若 𝑅>𝑑,可以减少之前的存款,把上界压到 𝑑,即 𝑅←𝑑。
  • 若 𝑎𝑖=0:

    • 若 𝑅<0,当前所有策略的余额都为负,必须存款。存款次数加一;存款后可把余额调到 [0,𝑑] 中任意值,所以令 𝐿=0,𝑅=𝑑。
    • 否则 𝑅≥0。若 𝐿<0,区间内存在余额 0,可以调整之前的存款额使当前余额为 0,不增加次数,令 𝐿=0。
    • 若 𝐿≥0,无需操作。

最后输出存款次数。

为什么区间内的余额都可达:初始时只有 0;非检查日只是整体平移;检查日若强制存款,区间扩为 [0,𝑑],否则把负的下界截到 0。每一步都没有丢失可达整数。

为什么次数最少:只有 𝑅<0 时,所有可达余额都为负,存款是强制的;其余时刻不存款不会使当前检查失败。非检查日不存款也不会影响之后,因为需要时可以在检查日再存,且不会增加次数。

复杂度

时间 𝑂(𝑛),空间 𝑂(1)。

参考

源码位置