嗯， 我这道题没AC，用了贪心算法。 下面是 65% 用例通过的代码， 留个纪念


import java.util.*;
import java.util.stream.Collectors;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < t; i++) {
            nums.clear();
            map.clear();
            int numSize = in.nextInt();
            for (int i1 = 0; i1 < numSize; i1++) {
                int tem = in.nextInt();
                Integer t1 = map.getOrDefault(tem, 0);
                if (t1 == 0) {
                    nums.add(tem);
                }
                t1++;
                map.put(tem, t1);
            }

            Collections.sort(nums);
            int[] maxNum = new int[nums.size()];


            int len = nums.size();

            maxNum[0] = map.get(nums.get(0));
            for (int j = 1; j < len; j++) {
                maxNum[j] = Math.max(maxNum[j - 1], map.get(nums.get(j)));
            }


            int cutNum = 0;
            int minCutNum = Integer.MAX_VALUE;
            for (int j = len - 1; j > 0; j--) {
                if (map.get(nums.get(j)) > maxNum[j - 1]) {
                    minCutNum = Math.min(minCutNum, cutNum);
                } else {
                    int cost = 0;
                    for (int k = 0; k < j; k++) {
                        if (map.get(nums.get(k)) >= map.get(nums.get(j))) cost += (map.get(nums.get(k)) - map.get(nums.get(j)) + 1);
                    }

                    minCutNum = Math.min(minCutNum, cutNum +cost);
                    cutNum += map.get(nums.get(j));
                }
            }

            minCutNum = Math.min(minCutNum , cutNum);

            if (minCutNum < Integer.MAX_VALUE){
                System.out.println(minCutNum);
            } else {
                System.out.println(0);
            }

        }
    }

}

接下来就是关于如何对上面的代码进行优化，防止超时了。 再这之前需要先说一下为什么这道选候选值的题不是动态规划

  • 对于不同的候选值没有共享的子问题
  • 选择某个x作为最大值的最优解，并不能通过选择更小x的最优解推导出来。
  • 没有明显的状态定义和状态转移方程

所以这题就是 枚举 + 贪心 然后看看咋优化性能。

对于每一个枚举到的候选值 x ， 它的需要删除的元素总数 为下面两个总数之和

  • 计算出所有比 x 大的数的数量之和
  • 计算出所有比 x 小 ， 同时数量要大于 x 的数， 需要删除最少元素使它的数量小于 x的数量 之和

所以这道题的关键就在于

  • 如何在枚举每一个值时， 高效的计算出上面两个总数， 并相加 与 现有的最小值 进行对比

针对第一点， 容易想到的就是 后缀和（有了后缀和就不用每次都相加一遍了） 针对第二点，我们需要先得出公式， 针对前面每一个小于x 的 数字 y 都有

  • y 的 出现次数 - （x 的出现次数 - 1 ） 然后我们要求和所以可以得出

  • 所有比x 小 且 出现次数在[x 的出现次数 ， 序列长度] 的数字的 出现次数之和 - 满足条件的数字的数量 * （x 的出现次数 - 1 ）

即 总删除次数 = 总频率和 - (freqX - 1) × 数字个数

所以假如说我们有一个数组 count， key即下标代表的是 频率（出现次数） ，value 代表的是 这个频率的存在数量， 那么假如说我们要计算 数字的频率在[2, 4] 之间需要删除的总次数时， 数字个数 = count[2] + count[3] + count[4]

然后如果有另一个数组 sum , key即下标代表的是 频率， value代表的是 频率 * 出现次数 那么总频率和 = sum[2] + sum[3] + sum[4]

如果上面count 和 sum 是前缀和数组， 我们就能很快的通过 比如 sum[4] - sum[1] 获取到结果 然后又因为假如我们是从小到大枚举候选值， 那么这个count 和 sum 在枚举的过程中肯定会变化， 由此，我们就可以想到用树状数组来解决眼前的问题。 最终的代码就不贴了 。。。