Educational Codeforces Round #105 1D Sokoban - Binary Search

Solution:

Classic binary search problem. We only consider the positive part. The negative part can be similar.

Let's consider to push boxes to $b_i$. We binary search $a$ with $b_i$ to find the largest $j$ so that $a_j\leq b_i$.

If there is a box at $b_i$. Which means $a_j=b_i$. Then we plus one to the basic result (base_ans++). No need for other things because push all boxes to here can't be the best solution.

If there is no box at $b_i$. Which means $a_j<b_i$. Then for all boxes between 0 and $a_j$, we push it to $b_i, b_i-1,b_i-2,...$. And then we binary search $b$ with the number of boxes between 0 and $a_j$ (Which is $j+1$). Find the smallest $k$ so that $b_k\geq j+1$. So the result of pushing all boxes to $b_i$ is $i-k+1+base\_ans$.

Enumerate $i$. We pick the maximum of results.

Code

Tips:

Convert the negative part to the positive. And run the solution again. It can make the implementation easier.