CF1987B K-Sort

题目描述

给定一个长度为 $n$ 的整数数组 $a$。

你可以进行如下操作任意次（可以为零次）：

• 首先，选择一个整数 $k$，满足 $1 \le k \le n$，并支付 $k+1$ 个硬币。
• 然后，选择恰好 $k$ 个下标，满足 $1 \le i_1 < i_2 < \ldots < i_k \le n$。
• 接着，对于每个 $x$ 从 $1$ 到 $k$，将 $a_{i_x}$ 增加 $1$。

请你求出使数组 $a$ 变为非递减（即 $a_1 \le a_2 \le \ldots \le a_n$）所需的最少硬币数。

输入格式

每组测试数据包含多组测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每组测试用例，输出一个整数，表示使 $a$ 变为非递减所需的最少硬币数。

输入输出样例 #1

输入 #1

5
3
1 7 9
5
2 1 4 7 6
4
1 3 2 4
1
179
9
344 12 37 60 311 613 365 328 675

输出 #1

0
3
2
0
1821

说明/提示

在第一个测试用例中，$a$ 已经是有序的，因此你不需要花费任何硬币。

在第二个测试用例中，最优的操作序列如下：

• 选择 $k=2$，下标为 $2$ 和 $5$：$[2, \color{red}{1}, 4, 7, \color{red}{6}] \rightarrow [2, 2, 4, 7, 7]$。这需要花费 $3$ 个硬币。

可以证明，无法用少于 $3$ 个硬币使 $a$ 变为非递减。

由 ChatGPT 4.1 翻译