CF1810C Make It Permutation

你有一个长度为 $n$ 的整数数组 $a$。你可以进行两种操作： - 从 $a$ 中移除一个整数。该操作的花费为 $c$。 - 在 $a$ 的任意位置（可以是开头、结尾或任意两个相邻元素之间）插入任意一个正整数 $x$。该操作的花费为 $d$。 你希望最终得到的数组是任意正长度的排列。请输出将数组变为排列所需的最小花费。注意，在操作过程中你可以让数组变为空，但最终数组必须至少包含一个整数。 长度为 $n$ 的排列是指包含 $1$ 到 $n$ 的 $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 \times 10^5$。

对于每组测试数据，输出一行，将数组变为排列所需的最小花费。

在第一个测试用例中，数组已经是一个排列，因此不需要任何操作。 在第二个测试用例中，我们可以移除数字 $5$、$6$，得到排列 $[1,2,3]$，花费为 $2$。注意我们也可以通过插入数字 $4$ 得到排列，但花费为 $5$。 在第三个测试用例中，我们可以移除除第一个数字 $1$ 以外的所有数字，花费为 $8$，最终数组为 $[1]$，它是长度为 $1$ 的排列。 在第四个测试用例中，我们可以移除除 $2$ 以外的所有数字，并在开头插入数字 $1$，花费为 $4+10=14$，最终数组为 $[1,2]$，它是长度为 $2$ 的排列。 由 ChatGPT 4.1 翻译