CF893D: Credit Card
只在检查日充钱;维护余额可达区间,区间全负时强制充一次,否则抬高下界,得到最少充钱次数。来源 Codeforces 893 D · 难度 Codeforces 1900 · 时间 2 s,空间 256 MB · 标签 贪心 / 模拟 / 区间 / 可行性
题目描述
有 天,账户初始余额为 ,余额上限为 。第 天晚上发生交易 :
- 若 ,账户增加 ;
- 若 ,账户减少 ;
- 若 ,检查余额,要求余额非负。
每个早晨可以存入任意正整数,但任意时刻余额都不能超过 。求最少需要在多少个早晨存款;无解输出 。
,,。
题解
存款只会抬高余额,因此不需要在非检查日存款:若某次存款发生在非检查日,把它推迟到下一次检查日,不会减少可行性,也不会增加次数。于是只需考虑 的检查日。
维护当前所有可达余额的区间 ,其中 是最小可达余额, 是最大可达余额;区间内的整数都可达,且当前存款次数不变。
初始时 。
若 ,令 ,。
- 若 ,无解。
- 若 ,可以减少之前的存款,把上界压到 ,即 。
若 :
- 若 ,当前所有策略的余额都为负,必须存款。存款次数加一;存款后可把余额调到 中任意值,所以令 ,。
- 否则 。若 ,区间内存在余额 ,可以调整之前的存款额使当前余额为 ,不增加次数,令 。
- 若 ,无需操作。
最后输出存款次数。
为什么区间内的余额都可达:初始时只有 ;非检查日只是整体平移;检查日若强制存款,区间扩为 ,否则把负的下界截到 。每一步都没有丢失可达整数。
为什么次数最少:只有 时,所有可达余额都为负,存款是强制的;其余时刻不存款不会使当前检查失败。非检查日不存款也不会影响之后,因为需要时可以在检查日再存,且不会增加次数。
复杂度
时间 ,空间 。
参考
- 题目链接:CF 893D Credit Card。
- 思路参考:Sshwy 做题总结。