← 返回题目列表

Codeforces · 1566/D1

D1. 座位安排(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是在此版本中 $$$n = 1$$$。

在电影院中,座位可以表示为具有 $$$n$$$ 行和 $$$m$$$ 列的表格。这些行用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。每行中的座位从左到右用连续整数编号:在第 $$$k$$$ 行中,所有行从 $$$m (k - 1) + 1$$$ 到 $$$m k$$$ 为 $$$1 \le k \le n$$$。

$$$1$$$$$$2$$$$$$\cdots$$$$$$m - 1$$$$$$m$$$$$$m + 1$$$$$$m + 2$$$$$$\cdots$$$$$$2 m - 1$$$$$$2 m$$$$$$2m + 1$$$$$$2m + 2$$$$$$\cdots$$$$$$3 m - 1$$$$$$3 m$$$$$$\vdots$$$$$$\vdots$$$$$$\ddots$$$$$$\vdots$$$$$$\vdots$$$$$$m (n - 1) + 1$$$$$$m (n - 1) + 2$$$$$$\cdots$$$$$$n m - 1$$$$$$n m$$$ 带有座位索引的桌子

有$$$nm$$$人想去电影院看一部新电影。它们用从 $$$1$$$ 到 $$$nm$$$ 的整数进行编号。你应该给每个人正好一个座位。

众所周知,在这个电影院中,座位指数越低,您就越能看到屏幕上发生的一切。第 $$$i$$$ 人的视力水平为 $$$a_i$$$。让我们将 $$$s_i$$$ 定义为座位索引,它将分配给第 $$$i$$$ 人。您希望为视力水平较低的人提供更好的位置,因此对于任何两个人 $$$i$$$, $$$j$$$ ,使得 $$$a_i < a_j$$$ 应该满足 $$$s_i < s_j$$$。

在您为所有人让座后,他们将开始就座。按照从$$$1$$$到$$$nm$$$的顺序,每个人进入大厅并坐在自己的座位上。为了到达他们的位置,该人将走到他们座位的那排,并开始从该排的第一个座位从左到右移动到他们的座位。虽然有些地方可以免费移动,但有些地方却已经坐满了人。一个人的不便程度等于他或她将经历的占用座位的数量。

举个例子:$$$m = 5$$$,该人拥有第一排$$$4$$$座位,第一排$$$1$$$、$$$3$$$、$$$5$$$座位已被占用,$$$2$$$和$$$4$$$座位空闲。此人的不便将是$$$2$$$,因为他将经过占用的座位$$$1$$$ 和$$$3$$$。

找出通过为所有人提供位置而可能产生的最小总不便(所有人的不便之和)(所有条件都应得到满足)。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$n = 1$$$, $$$1 \le m \le 300$$$) - 分别是行数和每行中的位置。

每个测试用例的第二行包含 $$$n \cdot m$$$ 整数 $$$a_1, a_2, \ldots, a_{n \cdot m}$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 人的视力水平。

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

输出

对于每个测试用例,打印一个整数——可以实现的最小总不便。

示例

输入 #1

4
1 3
1 2 3
1 5
2 1 5 3 3
1 2
2 1
1 6
2 3 2 1 1 1

输出 #1

3
6
0
1

注意

在第一个测试用例中,只有一种方法来安排人员,因为所有视线级别都是不同的。第一个人坐在第一个座位上,第二个人坐在第二个座位上,第三个人坐在第三个座位上。因此,第一人的不便将是$$$0$$$,第二人的不便将是$$$1$$$,第三人的不便将是$$$2$$$。总的不便之处为 $$$0 + 1 + 2 = 3$$$。

在第二个测试用例中,人们应该这样坐:$$$s_1 = 2$$$、$$$s_2 = 1$$$、$$$s_3 = 5$$$、$$$s_4 = 4$$$、$$$s_5 = 3$$$。总共带来的不便将是 $$$6$$$。