CF1852C Ina of the Mountain

为了让她的“Takodachi”小笨章鱼们征服世界，Ninomae Ina'nis（又名 Ina of the Mountain）命令 Hoshimachi Suisei 向它们投掷巨石。Ina 要求你，Kiryu Coco，帮忙选择巨石投掷的位置。 Ina 山上的小路上有 $n$ 只章鱼，编号为 $1, 2, \ldots, n$。第 $i$ 只章鱼的初始生命值为 $a_i$，其中 $1 \leq a_i \leq k$。 每块巨石会砸中编号为 $l, l+1, \ldots, r$ 的连续章鱼，其中 $1 \leq l \leq r \leq n$。你可以为每块巨石任意选择 $l$ 和 $r$ 的值。 每次巨石投掷后，被砸中的每只章鱼的生命值减少 $1$。然而，由于章鱼是不死的，一旦生命值降到 $0$，它们会立刻恢复到 $k$。 给定所有章鱼的初始生命值，求使所有章鱼的生命值都等于 $k$ 所需投掷巨石的最小次数。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^5$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^9$），分别表示章鱼的数量和生命值的上限。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le k$），表示每只章鱼的初始生命值。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出使所有章鱼的生命值都等于 $k$ 所需投掷巨石的最小次数。

在第一个测试用例中，最少需要投掷 $2$ 次巨石： - 第一次投掷巨石区间为 $[l,r] = [1,3]$。此时，章鱼的生命值变为 $[3, 1, 3, 3]$。 - 第二次投掷巨石区间为 $[l,r] = [2,2]$。此时，章鱼的生命值变为 $[3, 3, 3, 3]$。 在第二个测试用例中，最少需要投掷 $4$ 次巨石。对应的 $[l,r]$ 区间分别为 $[1,7], [2,6], [3,5], [4,4]$。 由 ChatGPT 4.1 翻译