2018-4-13模拟赛:C

2018-4-13模拟赛:C
这题暴力分70,呵呵,为什么还有人拿40的呢
Std可以转换成对于第i双鞋,所有满足a_j \le s_i的格子j可以走,一次最多可以从x走到x + d_i。不能走过去的情况只有一种:连续的不能走的格子的长度\ge d_i。所以我们可以把鞋子按s从大到小排个序,格子也排个序,用一个链表维护当前可以走的格子。对于当前处理的鞋子i,把链表中a_j \gt s_i的格子删掉,更新一下连续不能走的格子的长度的最大值,那就可以知道鞋子i的答案。复杂度是O(nlogn + blogb + n + b)

发表评论

电子邮件地址不会被公开。 必填项已用*标注