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$。我们然后把每次的结果都取最大就完事了。

代码

实现建议

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