CF1992B Angry Monk

为了庆祝康复，k1o0n 烤了一份长达 $n$ 米的巨型土豆砂锅。 然而，Noobish\_Monk 实在受不了土豆，于是决定毁掉 k1o0n 的美食。他把砂锅切成了 $k$ 块，长度分别为 $a_1, a_2, \dots, a_k$ 米。 k1o0n 并不喜欢这样。幸运的是，一切都可以修复。为此，k1o0n 可以进行以下两种操作之一： - 选择一块长度为 $a_i \ge 2$ 的砂锅，将其分成两块，长度分别为 $1$ 和 $a_i - 1$。这样，砂锅块数会增加 $1$； - 选择一块长度为 $a_i$ 的砂锅和另一块长度为 $a_j=1$ 的砂锅（$i \ne j$），将它们合并成一块长度为 $a_i+1$ 的砂锅。这样，砂锅块数会减少 $1$。 请你帮助 k1o0n 计算，最少需要多少次操作，才能将砂锅重新合并成一整块长度为 $n$ 的砂锅。 例如，如果 $n=5$，$k=2$，$a = [3, 2]$，最优操作如下： 1. 将长度为 $2$ 的砂锅分成长度为 $1$ 和 $1$ 的两块，得到 $a = [3, 1, 1]$。 2. 将长度为 $3$ 的砂锅和长度为 $1$ 的砂锅合并，得到 $a = [4, 1]$。 3. 将长度为 $4$ 的砂锅和长度为 $1$ 的砂锅合并，得到 $a = [5]$。

每个测试点包含多组测试用例。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。 每组测试用例包含两行。第一行为两个整数 $n$ 和 $k$（$2 \le n \le 10^9$，$2 \le k \le 10^5$），分别表示砂锅的总长度和被切成的块数。 第二行为 $k$ 个整数 $a_1, a_2, \ldots, a_k$（$1 \le a_i \le n - 1$，$\sum a_i = n$），表示 Noobish\_Monk 切出的每块砂锅的长度。 保证所有测试用例中 $k$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出 k1o0n 恢复砂锅所需的最少操作次数。

由 ChatGPT 4.1 翻译