社区讨论

CF Round822 D题这个做法为什么错了

AAndrewzdm
学术版参与者 5已保存回复 13

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@lo7ym6az
此快照首次捕获于
2023/10/27 09:53
2 年前
此快照最后确认于
2023/10/27 09:53
2 年前
查看原帖
题目链接
RT，是一个不同于题解的思路。
首先我们可以钦定这个 slime 从左边的出口还是从右边的出口出去，然后判定是否可行，以从左边（坐标00）出去为例。
首先计算往左边走各时刻的前缀和，得到前缀和序列 ss。若前缀和一直非负那么就可以直接走出去，否则就必须吞右边的 slime。
考虑逐个按顺序将吞右边的 slime 的值插入 ss 中并更新 ss。（ss 是前缀和，所以会把当前位置及之后的所有位置都加上这个健康值）
设要吞的右边的那个 slime 的健康值是 xx。
  1. 若 x<0x\lt0，那么为了不go die，在某个位置吞了它之后当前位置的健康值不能为负，否则就没机会了。然后这个位置要尽可能地靠前，这样后面吞大于 00 的健康值的时候更有机会把原序列 ss 中的负值调正。
  2. 若 x≥0x\ge0，直接在当前的位置上吞了 xx。
持续调整，直至前缀和恒非负结束，可行。
感觉这个贪心策略没什么问题，一直 WA on test 4，而且是在第4个数据点的第1204组数据错了……
代码贴二楼

回复

共 13 条回复，欢迎继续交流。

正在加载回复...