← 返回题目列表

Codeforces · 1810/C

C. 进行排列

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

您有一个长度为 $$$n$$$ 的整数数组 $$$a$$$。您可以进行两种操作。

- 从 $$$a$$$ 中删除一个整数。此操作的成本为$$$c$$$。
- 将任意正整数 $$$x$$$ 插入到 $$$a$$$ 的任意位置(前面、后面或任意两个连续元素之间)。此操作的成本为$$$d$$$。

您希望使最终数组成为任意正长度的排列。请输出这样做的最低成本。请注意,您可以在操作过程中将数组清空,但最终数组必须至少包含一个整数。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。他们的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$c$$$、$$$d$$$ ($$$1 \le n \le 10^5$$$、$$$1 \le c,d \le 10^9$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$)。

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

输出

对于每个测试用例,在一行中输出使最终数组成为排列的最小成本。

示例

输入 #1

8
3 3 3
1 2 3
5 1 5
1 2 3 5 6
5 2 3
1 1 1 3 3
5 1 10
2 4 6 8 10
6 2 8
7 3 5 4 4 8
4 10 1
1 2 6 7
4 3 3
2 5 8 7
2 1000000000 1
1000000000 1

输出 #1

0
2
8
14
20
3
12
999999998

注意

在第一个测试用例中,数组已经是一个排列,因此不需要进行操作。

在第二个测试用例中,我们可以删除数字 $$$5$$$、$$$6$$$ 以获得成本 $$$2$$$ 的排列 $$$[1,2,3]$$$。请注意,我们还可以通过插入数字 $$$4$$$ 来获得排列,但它的成本为 $$$5$$$。

在第三个测试用例中,我们可以删除除第一个数字 $$$1$$$ 之外的所有数字。花费$$$8$$$,最终的数组是$$$[1]$$$,它是长度$$$1$$$的排列。

在第四个测试用例中,我们可以删除除$$$2$$$之外的所有数字,并在第一个位置插入一个数字$$$1$$$。花费$$$4+10=14$$$,最终的数组是$$$[1,2]$$$,它是长度$$$2$$$的排列。