P7622 [AHOI2021 Junior] Pit

AHOI2021 Junior Group T2. **You may choose to skip the background section.** On the way to buy things, Xiaoxue breathed in several mouthfuls of smog and finally sneezed. The bad weather and the depressing atmosphere made Xiaoxue feel worse and worse, and then she started complaining: “Sigh! Today I got ‘tricked’ by an unreliable classmate again, and it wasted a lot of my time.” “The midterm is still far away. Why be so anxious? Don’t push yourself so hard. Come and take a look at a game that has been popular recently in Ququ Country.” Xiaoxue got interested when she saw the game: it looked quite stress-relieving.

The game is played on a number line that extends infinitely to the left and right. There are $n$ fleas and $m$ pits on it, and they can both be modeled as points on the number line. In each round, the player must choose to make all fleas jump together one unit to the left or one unit to the right. If a point representing a flea coincides with a point representing a pit, the flea will fall into the pit, scream, and then die. The upset Xiaoxue wants to kill all fleas in the shortest time. Please help her compute the minimum number of rounds needed.

The first line contains two positive integers $n,m$ separated by spaces. The second line contains $n$ integers $x_1,x_2,\ldots,x_n$ separated by spaces, where $x_i$ is the initial coordinate of the $i$-th flea. The third line contains $m$ integers $y_1,y_2,\ldots,y_m$ separated by spaces, where $y_i$ is the coordinate of the $i$-th pit. The input guarantees that all of these $n+m$ coordinates are pairwise distinct.

Only one line with one integer, the minimum number of rounds needed to kill all fleas.

[Sample 1 Explanation] In the first round, make all fleas jump one step to the right. The second flea falls into the first pit, and the remaining two fleas are at $4, 3$ respectively. In the next four rounds, make all fleas jump to the left. Both fleas fall into the first pit, and the game ends. [Constraints and Notes] **Note: The input size of this problem is large, so please avoid overly slow input methods.** - For $20\%$ of the testdata, $1 \le n \le 20$, $1 \le m \le 300$. - For another $20\%$ of the testdata, $1 \le n,m \le 300$. - For another $20\%$ of the testdata, $1 \le x_i,y_i \le 2000$. - For another $10\%$ of the testdata, $1 \le n,m \le 2000$. - For another $10\%$ of the testdata, $m=2$. - For $100\%$ of the testdata, $1 \le n,m \le 2 \times 10^5$, $-10^9 \le x_i,y_i \le 10^9$. Translated by ChatGPT 5