#CW45. MEX(mex)
MEX(mex)
题目描述
小 W 有一个长度为 的正整数数组 。定义数组的 mex 为没有在数组中出现的最小正整数。
一次操作可以选择一个下标 和一个整数 ,满足 且 ,支付 的代价并把 改为 。操作可以进行任意次。
请计算使数组的 mex 恰好等于 所需的最小总代价。如果无法做到,输出 。
输入格式
第一行一个正整数 ,表示测试数据组数。
接下来每组数据包含两行:
- 第一行两个整数 ;
- 第二行 个正整数 。
输出格式
对于每组数据输出一行一个整数,表示最小总代价;无解时输出 。
样例 1 输入
4
4 3
2 3 4 5
3 2
3 2 1
5 4
1 1 2 8 9
6 3
2 2 4 7 7 10
样例 1 输出
2
1
5
1
数据范围
对所有数据,保证 ,,,且 。
本题采用捆绑测试并开启子任务依赖。只有某个子任务中的所有测试数据以及它所依赖的子任务均通过时,才能获得该子任务的分数。
| 子任务 | 分值 | 测试点 | 附加限制 | 依赖 |
|---|---|---|---|---|
| 1 | 25 | 无 | ||
| 2 | 所有 两两不同 | |||
| 3 | 1, 2 | |||
| 4 | 无附加限制 | 1, 2, 3 |