310288: CF1810C. Make It Permutation
Description
You have an integer array $a$ of length $n$. There are two kinds of operations you can make.
- Remove an integer from $a$. This operation costs $c$.
- Insert an arbitrary positive integer $x$ to any position of $a$ (to the front, to the back, or between any two consecutive elements). This operation costs $d$.
You want to make the final array a permutation of any positive length. Please output the minimum cost of doing that. Note that you can make the array empty during the operations, but the final array must contain at least one integer.
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
InputEach test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Their description follows.
The first line of each test case contains three integers $n$, $c$, $d$ ($1 \le n \le 10^5$, $1 \le c,d \le 10^9$).
The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \le a_{i} \le 10^9$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output in one line the minimum cost to make the final array a permutation.
ExampleInput8 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 1Output
0 2 8 14 20 3 12 999999998Note
In the first test case, the array is already a permutation, so there's no need for operations.
In the second test case, we can remove numbers $5$, $6$ to get the permutation $[1,2,3]$ in cost $2$. Note that we can also get a permutation by inserting a number $4$, but it costs $5$.
In the third test case, we can just remove all the numbers except for the first number $1$. It costs $8$, and the final array is $[1]$, which is a permutation of length $1$.
In the fourth test case, we can remove all the numbers except for $2$, and insert a number $1$ to the first position. It costs $4+10=14$, and the final array is $[1,2]$, which is a permutation of length $2$.
Input
题意翻译
给定一个长为 $n$ 的序列 $a$，你可以进行以下两个操作： 1. 删除 $a$ 中的任意一个数字，花费为 $c$。 1. 往 $a$ 的任意位置插入一个数字，花费为 $d$。 求最后得到一个任意长度的排列的最小花费。 注：最终排列长度不能为 $0$，但操作中序列长度可以为 $0$。Output
给定一个长度为n的整数数组a。你可以进行两种操作：
1. 从a中移除一个整数，此操作花费c。
2. 在a的任意位置插入一个任意的正整数x（可以插在前面、后面或任意两个连续元素之间），此操作花费d。
你的目标是使得最终数组是一个任意正长度n的排列。请输出实现这一目标的最小花费。注意，在操作过程中数组可以为空，但最终数组必须至少包含一个整数。
一个长度为n的排列是一个由1到n的n个不同整数以任意顺序组成的数组。例如，[2,3,1,5,4]是一个排列，但[1,2,2]不是排列（因为2在数组中出现了两次），[1,3,4]也不是排列（因为n=3但在数组中出现了4）。
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含三个整数n、c、d（1≤n≤10^5，1≤c,d≤10^9）。
每个测试用例的第二行包含n个整数a1、a2、…、an（1≤ai≤10^9）。
保证所有测试用例的n之和不超过2×10^5。
输出数据格式：
对于每个测试用例，输出一行，表示使最终数组成为一个排列的最小花费。
示例：
输入：
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
输出：
0
2
8
14
20
3
12
999999998
注意：
在第一个测试用例中，数组已经是一个排列，所以不需要操作。
在第二个测试用例中，我们可以移除数字5、6，以得到排列[1,2,3]，花费2。注意，我们也可以通过插入数字4来得到一个排列，但这需要花费5。
在第三个测试用例中，我们可以移除除了第一个数字1以外的所有数字。这需要花费8，最终数组是[1]，这是一个长度为1的排列。
在第四个测试用例中，我们可以移除除了2以外的所有数字，并在第一个位置插入数字1。这需要花费4+10=14，最终数组是[1,2]，这是一个长度为2的排列。题目大意： 给定一个长度为n的整数数组a。你可以进行两种操作： 1. 从a中移除一个整数，此操作花费c。 2. 在a的任意位置插入一个任意的正整数x（可以插在前面、后面或任意两个连续元素之间），此操作花费d。 你的目标是使得最终数组是一个任意正长度n的排列。请输出实现这一目标的最小花费。注意，在操作过程中数组可以为空，但最终数组必须至少包含一个整数。 一个长度为n的排列是一个由1到n的n个不同整数以任意顺序组成的数组。例如，[2,3,1,5,4]是一个排列，但[1,2,2]不是排列（因为2在数组中出现了两次），[1,3,4]也不是排列（因为n=3但在数组中出现了4）。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数n、c、d（1≤n≤10^5，1≤c,d≤10^9）。 每个测试用例的第二行包含n个整数a1、a2、…、an（1≤ai≤10^9）。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一行，表示使最终数组成为一个排列的最小花费。 示例： 输入： 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 输出： 0 2 8 14 20 3 12 999999998 注意： 在第一个测试用例中，数组已经是一个排列，所以不需要操作。 在第二个测试用例中，我们可以移除数字5、6，以得到排列[1,2,3]，花费2。注意，我们也可以通过插入数字4来得到一个排列，但这需要花费5。 在第三个测试用例中，我们可以移除除了第一个数字1以外的所有数字。这需要花费8，最终数组是[1]，这是一个长度为1的排列。 在第四个测试用例中，我们可以移除除了2以外的所有数字，并在第一个位置插入数字1。这需要花费4+10=14，最终数组是[1,2]，这是一个长度为2的排列。