题解：CF1494C 1D Sokoban

· · 题解

前言

模拟赛的T2，来写一篇题解。

题解

通过推导可以发现位置为正只能往右，位置为负只能往左（因为你不可能跳过一个箱子），那么我们就可以分成正负两部分处理。通过推导可以发现第一个箱子一定是推到特殊点上最优。可以通过二分求出第一个箱子推到当前这个点有多少个箱子，描述可能有点问号，放张图:

然后再二分出这个区间有多少个特殊点，最后加上没有被推过的箱子本来就在特殊点上的情况，就得出了答案。

C++ 党可以使用 std::lower_bound 和 std::upper_bound。