Educational Codeforces Round #105 1D Sokoban - 二分

题意

经典1维推箱子。

有$n$个箱子,分别位于数组$a$上。现在有$m$个目标位置,在数组$b$里。

现在你从0出发,你随便左右怎么走都行,你一次可以推动无数个箱子,但是你不能拉箱子。现在问你,最多能把多少箱子推到目标位置。

题解

经典二分。我们只考虑正数的部分,负数部分其实同理。

我们考虑把箱子推到$b_i$。我们根据$b_i$二分$a$找到第一个$a_j\leq b_i$。

如果$b_i$上恰好有个箱子,也就是$a_j=b_i$。那么我们把一个基础结果+1(base_ans++)。无需额外操作,因为把箱子推到这里一定不是最优解。

如果$b_i$上不存在箱子,也就是$a_j<b_i$。那这意味着0到$a_j$所有的箱子都被推到了$b_i, b_i-1,b_i-2,...$。于是我们再根据0到$a_j$箱子的个数二分$b$($j+1$个箱子)。找出第一个$b_k\geq j+1$。于是推到$b_i$的结果就是$i-k+1+base\_ans$。

枚举$i$。我们然后把每次的结果都取最大就完事了。

代码

Submission #114380700 - Codeforces
Codeforces. Programming competitions and contests, programming community

实现建议

把负的那一半转成正的,再做跑一次。实现起来会简单一些。