Save More Mice
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 1000
Tags: binary search, greedy, greedy

There are one cat, $$$k$$$ mice, and one hole on a coordinate line. The cat is located at the point $$$0$$$, the hole is located at the point $$$n$$$. All mice are located between the cat and the hole: the $$$i$$$-th mouse is located at the point $$$x_i$$$ ($$$0 < x_i < n$$$). At each point, many mice can be located.

In one second, the following happens. First, exactly one mouse moves to the right by $$$1$$$. If the mouse reaches the hole, it hides (i.e. the mouse will not any more move to any point and will not be eaten by the cat). Then (after that the mouse has finished its move) the cat moves to the right by $$$1$$$. If at the new cat's position, some mice are located, the cat eats them (they will not be able to move after that). The actions are performed until any mouse hasn't been hidden or isn't eaten.

In other words, the first move is made by a mouse. If the mouse has reached the hole, it's saved. Then the cat makes a move. The cat eats the mice located at the pointed the cat has reached (if the cat has reached the hole, it eats nobody).

Each second, you can select a mouse that will make a move. What is the maximum number of mice that can reach the hole without being eaten?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le k \le 4 \cdot 10^5$$$). The second line contains $$$k$$$ integers $$$x_1, x_2, \dots x_k$$$ ($$$1 \le x_i < n$$$) — the initial coordinates of the mice.

It is guaranteed that the sum of all $$$k$$$ given in the input doesn't exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case output on a separate line an integer $$$m$$$ ($$$m \ge 0$$$) — the maximum number of mice that can reach the hole without being eaten.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
3
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1
12 11
1 2 3 4 5 6 7 8 9 10 11

Example output:
3
1
4

Editorial:
Let's solve the problem using a linear search. Let $$$m$$$ be the number of mice we are trying to save. Then it is more efficient to save $$$m$$$ mice such that they are the closest ones to the hole. Let $$$r_i$$$ be the distance from the $$$i$$$-th mouse to the hole ($$$r_i = n - x_i$$$). Denote $$$R := \sum\limits_{i = 1}^m r_i$$$. Let's prove that these mice will be saved if and only if $$$R < n$$$.
The necessary condition. Suppose we can save the mice and $$$R \ge n$$$. Since only one mouse can be moved in one second, the following will happen: $$$m - 1$$$ of mice will already be saved and one mouse will have to be saved. When it's been $$$q$$$ seconds, then the distance from the cat to the hole will be equal to $$$n - q$$$, and the distance from the mouse to the hole will be equal to $$$R - q$$$ (since all other mice are already in the hole, their distances to the hole are equal to $$$0$$$, so the sum of the distances from all mice to the hole at the current time is exactly equal to the distance to the hole from one remaining mouse). Since $$$R - q \ge n - q$$$, the distance from the mouse to the hole is greater than or equal to the distance from the cat to the hole. But this cannot be, because both the mice and the cat move only to the right, and all mice met by the cat are eaten. So, $$$R < n$$$.
Sufficient condition. Suppose $$$R < n$$$. If $$$R = 0$$$, then all the mice are already in the hole, i.e. they are saved. Suppose $$$R > 0$$$. Let's move any mouse, then the cat. Suppose the cat ate at least one of the mice. This mouse is definitely not the one that was moved. Then the distance from it to the eaten mouse was equal to $$$1$$$, i.e. the distance from it to the hole was equal to the distance from the eaten mouse to the hole plus $$$1$$$. The distance from the moved mouse to the hole was at least $$$1$$$. So, $$$R \ge r_s + r_m$$$, where $$$r_s = n - 1$$$ is the distance from the eaten mouse to the hole, $$$r_m \ge 1$$$ is the distance from the moved mouse to the hole. So, $$$R \ge n - 1 + 1 = n$$$, but it's false. Therefore, none of the mice will be eaten on the first move. Then the distance from the cat to the hole will be equal to $$$n - 1$$$, the total distance from the mice to the hole will be equal to $$$R - 1$$$. $$$R - 1 < n - 1$$$, i.e. now we have to solve a similar problem for smaller $$$R$$$ and $$$n$$$. So $$$R$$$ will be gradually decreased to $$$0$$$, while no mouse will be eaten. So, if $$$R < n$$$, all the mice will be saved.
Thus, to solve the problem, we need to find the maximum $$$m$$$ such that the sum of the distances from the $$$m$$$ nearest mice to the hole is less than $$$n$$$.