优先队列

摘要：在2022年2月18日的可信科目一考试中第三道题遇到了一道优先队列的题目，其实之前刷题中也遇到了优先队列的题目，但是当时只是简单看了下，考试中临场发挥没想起用优先队列导致题目部分通过，这里通过这道题目也记录一下优先队列用法，加深记忆。 题目是这样的，有一个供应商价格和库存的二维数组，例如[[9,5],[11,4]]。每购买一次供应商的价格增加1，库存减少1，求购买指定次数的最小金额？ 例如：输入4， 第一次购买花费9，此时

在2022年2月18日的可信科目一考试中第三道题遇到了一道优先队列的题目，其实之前刷题中也遇到了优先队列的题目，但是当时只是简单看了下，考试中临场发挥没想起用优先队列导致题目部分通过，这里通过这道题目也记录一下优先队列用法，加深记忆。

题目是这样的，有一个供应商价格和库存的二维数组，例如[[9,5],[11,4]]。每购买一次供应商的价格增加1，库存减少1，求购买指定次数的最小金额？ 例如：输入4， 第一次购买花费9，此时变成[10,4] 第二次购买花费10，此时变成[11,3] 第三次购买花费11，因为两个单价都是11，所以买哪个都可以，此时变为[12,2]或者[12,3] 第四次购买花费11 所以最小花费金额为41。

public int getMinAmount(int[][] supplies, int count) {
          
   
        int minAmount = 0;
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
          
   
            @Override
            public int compare(int[] o1, int[] o2) {
          
   
                if (o1[0] == o2[0]) {
          
   
                    return o2[1] - o1[1];
                } else {
          
   
                    return o1[0] - o2[0];
                }
            }
        });
        for (int[] arr : supplies) {
          
   
            queue.offer(arr);
        }
        while (!queue.isEmpty() && count > 0) {
          
   
            int[] supply = queue.poll();
            if (supply[1] > 0) {
          
   
                minAmount += supply[0];
                count--;
                int[] newSupply = new int[]{
          
   ++supply[0], --supply[1]};
                queue.offer(newSupply);
            }
        }
        return minAmount;
    }

优先队列构建的时候需要实现一个Comparator类来自定义排序逻辑，队列在插入元素的时候就会根据我们定义的排序规则来插入到指定的位置，那么按照这道题的逻辑，我们可以按照商品价格升序排序，保证队首的永远都是价格最低的。同时按照库存降序排序，价格一样时，优先买库存最多的。

/**
     * 优先队列
     */
    public static void queueSum(String[] s){
          
   
        Queue<Integer> queue = Arrays.stream(s).map(Integer::parseInt)
                .sorted().collect(Collectors.toCollection(PriorityQueue::new));
        int sum = 0;
        while (queue.size()>1){
          
   
            int seg = queue.poll()+queue.poll()+queue.poll();
            sum+=seg;
            //add后会自动根据值进行从小到大排列
            queue.add(seg);
        }
        System.out.println(sum);
    }