本题关联比赛
NOIP2023模拟赛5

关于排序的近10条评论(全部评论)
$O(n^2)$ DP后2个点会T，要用数状数组/线段树维护ムラサメ 2023-11-17 16:06 2楼
没有离散化的后果(慢的一批) ┭┮﹏┭┮ 2023-11-17 14:06 1楼

3937. [YNOI2019] 排序

★★ 输入文件：sort.in 输出文件：sort.out 简单对比
时间限制：1 s 内存限制：256 MiB

对于一个数列 $\{7,1,2,3\}$ 进行排序，我们可以把 $7$ 从头移动到尾。但是这个操作的成本是 $7$，并不是最佳的。最佳的排序方式是将连续的 $1,2,3$ 移动到 $7$ 的前面。这样的话，总的操作成本就是 $1+2+3=6$，比之前的成本 $7$ 要小。

你的任务是，对于一个给定的数列，输出对这个数列进行排序的最小成本。

每个输入文件包含多组数据。

输入文件的第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

每组数据包含 $2$ 行；

第一行包含一个正整数 $n$，代表数列中元素的个数。

第二行包含 $n$ 个整数，两个数之间以一个空格隔开，代表数列中的元素 $k_i$。

输出文件包含 $T$ 行，分别对应 $T$ 组数据的答案，即对数列进行排序的最小成本。

1
4
7 1 2 3

对于 $20\%$ 的数据：$0 \lt n \le 20$。

对于 $80\%$ 的数据：$0 \lt n \le 1000$。

对于 $100\%$ 的数据：$0 \lt n \le 10^5,0 \lt k_i \le 10^7,T \le 10$。