Save More Mice

题意翻译

**题目描述：** 坐标轴上有一只猫，$k$ 只老鼠和一个洞口。其中猫在坐标为 $0$ 的位置，洞口在坐标为 $n$ 的位置，所有的老鼠都在猫和洞口之间，其中第 $i$ 只老鼠在 $x_i$ 的位置。可能有多只老鼠在同一个位置上。 在每一秒钟，将会**依次**执行以下行动： - **其中一只**老鼠会向右移动 $1$ 的位置，如果一个老鼠到达洞口，它会隐藏起来（这只老鼠将不会再移动到任何位置，也不会被猫吃掉）。 - 猫会向右移动 $1$ 的位置，并会吃掉它到达的位置上的老鼠（被吃掉的老鼠将不能再移动）。 直到所有的老鼠都已经隐藏起来或已经被吃掉。 每一秒钟，你都可以选择移动的老鼠，请你求出最多可以保护多少只老鼠安全到达洞口并隐藏起来。 **输入格式：** 本题包含多组数据。 输入的第一行包含一个正整数 $t$，表示数据组数。 每组数据包含两行，其中第一行包含两个整数 $n$ 和 $k$； 第二行包含 $k$ 个整数 $x_1,x_2,\ldots,x_k$，表示老鼠的初始位置。 **输出格式：** 对于每组数据，输出一行一个非负整数 $m$，表示能保护的老鼠的最大数量。 **数据范围：** - $1 \le t \le 10^4$； - $2 \le n \le 10^9$； - $1 \le k \le 4 \times 10^5$； - $1 \le x_i <n$。 Translated by @BurningEnderDragon, 2021.10.14

题目描述

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?

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

3
1
4