CF1468D Firecrackers

考虑一条可以被划分为 $n$ 个 $1 \times 1$ 正方形格子的长走廊。这些格子从左到右编号为 $1$ 到 $n$。 在这条走廊里有两个人，一个是流氓，一个是保安。最开始，流氓在第 $a$ 个格子，保安在第 $b$ 个格子（$a \ne b$）。  这是其中一种可能的情况。走廊由 $7$ 个格子组成，流氓在第 $3$ 个格子，保安在第 $6$ 个格子（$n = 7$，$a = 3$，$b = 6$）。流氓口袋里有 $m$ 个鞭炮，第 $i$ 个鞭炮在点燃后 $s_i$ 秒爆炸。 每一秒会依次发生以下事件（顺序如下，且每步都必须执行）： 1. 首先，流氓可以移动到相邻的格子（从第 $i$ 个格子可以移动到第 $i+1$ 或第 $i-1$ 个格子，且不能离开走廊），或者留在原地。如果流氓不移动，他可以点燃并丢下一个鞭炮。流氓不能移动到保安所在的格子； 2. 其次，已经被丢下的某些鞭炮可能会爆炸。具体来说，如果第 $j$ 个鞭炮在第 $T$ 秒被丢下，那么它会在第 $T+s_j$ 秒爆炸（例如，如果 $s_j=2$ 的鞭炮在第 $4$ 秒被丢下，它会在第 $6$ 秒爆炸）； 3. 最后，保安向流氓靠近一格。如果保安移动到了流氓所在的格子，流氓就会被抓住。 显然，由于走廊是有限的，流氓迟早会被抓住。他的目标是在被抓住前让尽可能多的鞭炮爆炸；也就是说，他会采取最优策略，使得在被抓住前爆炸的鞭炮数量最大。 你的任务是计算，在流氓采取最优策略的情况下，最多能有多少个鞭炮在他被抓住前爆炸。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例包含两行。第一行包含四个整数 $n$、$m$、$a$ 和 $b$（$2 \le n \le 10^9$；$1 \le m \le 2 \times 10^5$；$1 \le a, b \le n$；$a \ne b$），分别表示走廊的长度、鞭炮数量、流氓的初始位置和保安的初始位置。 第二行包含 $m$ 个整数 $s_1, s_2, \ldots, s_m$（$1 \le s_i \le 10^9$），其中 $s_i$ 表示第 $i$ 个鞭炮从点燃到爆炸所需的时间。 保证所有测试用例的 $m$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示流氓在被抓住前最多能引爆的鞭炮数量。

在第一个测试用例中，流氓可以按如下方式行动： - 第 1 秒：丢下第 2 个鞭炮，它将在第 5 秒爆炸。保安移动到第 5 个格子； - 第 2 秒：移动到第 2 个格子。保安移动到第 4 个格子； - 第 3 秒：丢下第 1 个鞭炮，它将在第 4 秒爆炸。保安移动到第 3 个格子； - 第 4 秒：移动到第 1 个格子。第 1 个鞭炮爆炸。保安移动到第 2 个格子； - 第 5 秒：留在第 1 个格子。第 2 个鞭炮爆炸。保安移动到第 1 个格子并抓住流氓。 由 ChatGPT 4.1 翻译