2024美团秋招第一场笔试

解题思路：

这道题的难点在于计算Mex以及每次执行一次只删除第一个数组中的数字时，要及时更新Mex。我们假设不执行操作1，直接删除数组中全部数字的花费，此时就是Mex(a)=6，输入的花费系数k=3，此时totalCost = 3 * 6 = 18，因此首先假设最低花费minCost = totalCost = 18。然后计算MEX，即使用while()循环，查看哈希表中是否存在关键字MEX(为什么用哈希表存数字，下面说。)，如果MEX包含在哈希表中则MEX++,因为题目中已经说了，Mex(a)即在数组中未出现过的最小非负整数。最后是计算最小成本，因此最小成本是从总成本(每次执行操作1后的成本基本上都是不一样的)和直接删除整个数组(操作2)的花费成本相比较得出的最小值。

接着说一下为什么要使用集合，因为题目中没有特别说明数组中没有重复的值，即可能存在重复的数组元素，利用哈希表中的键值关系，用键来存储每个数组元素出现的次数，用值来表示该数组元素的值。最后一定要用Long类型的变量，用int类型的会报错。

下面是Java代码：

package jxkjsfdx.lgq;
import java.util.*;

public class Demo01 {
    public static void main(String[] args) {
        removeArray();

    }

    public static void removeArray() {
        Scanner scanner = new Scanner(System.in);
        long t = scanner.nextLong();

        while (t-- > 0) {
            long n = scanner.nextLong(); // 数组长度
            long k = scanner.nextLong(); // 删除整个数组的花费系数
            long x = scanner.nextLong(); // 单个删除的花费

            Map<Long, Long> hashMap = new HashMap<>();
            long[] a = new long[(int) n];

            for (long i = 0; i < n; i++) {
                a[(int) i] = scanner.nextLong();
                // 统计数组中每个元素出现的次数;如果元素已经存在于 hashMap 中，就增加其计数；如果不存在，则从0开始计数。
                hashMap.put(a[(int) i], hashMap.getOrDefault(a[(int) i], 0L) + 1);
            }

            // 计算MEX
            long minMiss = 0;
            while (hashMap.containsKey(minMiss)) {
                minMiss++;
            }

            long totalCost = k * minMiss; // 一开始就删除整个数组
            long minCost = totalCost;
            for (long i = 0; i < n; i++) {
                long currentValue = a[(int) i];
                System.out.println("当前MEX是：" + minMiss);
                System.out.println("当前总花费是：" + totalCost);

                // 更新 hashMap
                if (hashMap.get(currentValue) > 1) {
                    hashMap.put(currentValue, hashMap.get(currentValue) - 1);
                } else {
                    hashMap.remove(currentValue);
                }

                // 计算新的 mex
                minMiss = 0;   // 每次将minMiss置0，求出在不同的操作1下的MEX
                while (hashMap.containsKey(minMiss)) {
                    minMiss++;
                }

                // 计算当前结果
                minCost = Math.min(totalCost, (i + 1) * x + k * minMiss); // (i + 1) 是当前删除的元素数量
            }
            // 输出最小成本
            System.out.println("最小成本是：" + minCost);
        }

        scanner.close();
    }
}