首页 > 试题广场 >

小美的数组删除

[编程题]小美的数组删除
  • 热度指数：4534 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小美有一个长度为 n 的数组 a_1,a_2,\dots,a_n ，他可以对数组进行如下操作：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 删除第一个元素 a_1，同时数组的长度减一，花费为 x。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 删除整个数组，花费为 k\times \operatorname{MEX}(a) （其中 \operatorname{MEX}(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 \operatorname{MEX} 为 3 ）。
\,\,\,\,\,\,\,\,\,\,小美想知道将 a 数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述:
\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T\ (1\le T\le 1000) 代表数据组数，每组测试数据描述如下：
\,\,\,\,\,\,\,\,\,\,第一行输入三个正整数 n, k, x\ (1 \leq n \leq 2\times 10^5,\ 1 \leq k, x \leq 10^9) 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\ (0 \leq a_i \leq n)，表示数组元素。
\,\,\,\,\,\,\,\,\,\,除此之外，保证所有的 n 之和不超过 2\times 10^5。


输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。
示例1

输入

1
6 3 3
4 5 2 3 1 0

输出

15

说明

\,\,\,\,\,\,\,\,\,\,若不执行操作一就全部删除，\operatorname{MEX}\{4,5,2,3,1,0\}=6，花费 18 ；
\,\,\,\,\,\,\,\,\,\,若执行一次操作一后全部删除，\operatorname{MEX}\{5,2,3,1,0\}=4，花费 3+12 ；
\,\,\,\,\,\,\,\,\,\,若执行两次操作一后全部删除，\operatorname{MEX}\{2,3,1,0\}=4，花费 6+12 ；
\,\,\,\,\,\,\,\,\,\,若执行三次操作一后全部删除，\operatorname{MEX}\{3,1,0\}=2，花费 9+6 ；
\,\,\,\,\,\,\,\,\,\,若执行四次操作一后全部删除，\operatorname{MEX}\{1,0\}=2，花费 12+6 ；
\,\,\,\,\,\,\,\,\,\,若执行五次操作一后全部删除，\operatorname{MEX}\{0\}=1，花费 15+3 ；
\,\,\,\,\,\,\,\,\,\,若执行六次操作一，\operatorname{MEX}\{\}=0，花费 18 ；
算法知识视频讲解
开通博客

暂无题解

问题信息

难度：
24条回答 2645浏览

热门推荐

相关试题

小美的数组删除

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号