题解 | #吃汉堡#

题目：每天有a[i]个鸡肉汉堡和b[i]个牛肉汉堡，持续吃n天，保证每天吃的汉堡数量不同，要求在此汉堡数量最多大的前提下每天吃牛肉汉堡的数量最少，求最终吃的牛肉汉堡的数量

方法一：优先级队列+贪心

思路：

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。

在本题中，我们要先保证每天吃的汉堡数量最多，再保证牛肉汉堡的数量最少，因此维护一个最大堆存储每天所吃汉堡数量，用一个哈希表存储每天吃的汉堡数量，自定义类Ham存储当天鸡肉汉堡数量和牛肉汉堡数量以及汉堡总数，当堆中元素不在哈希表中则直接加入哈希表，同时记录牛肉汉堡的数量，如果在哈希表中，则我们需要判断该元素的牛肉汉堡数量是否大于0，如果有牛肉汉堡，则减少的是牛肉汉堡的数量，否则，只是减少鸡肉汉堡的数量。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型
     */
    public class Ham{
        int chicken,beef;
        int sum;
        Ham(int chicken,int beef){
            this.chicken=chicken;
            this.beef=beef;
            this.sum=this.chicken+this.beef;
        }
    }
    public long EatingHamburger (int n, int[] a, int[] b) {
        // write code here
        Set<Integer>set=new HashSet<>();
        PriorityQueue<Ham>q=new PriorityQueue<>(new Comparator<Ham>(){
            public int compare(Ham x,Ham y){
                return y.sum-x.sum;
            }
        });
        for(int i=0;i<n;i++){
            q.offer(new Ham(a[i],b[i]));
        }
        int num=0;//牛肉数量
        while(!q.isEmpty()){
            Ham curr=q.poll();
            int sum=curr.sum;
            int beef=curr.beef;
            if(!set.contains(sum)){//先保证汉堡数量最多且不重复
                set.add(sum);
                num+=beef;
            }
            else{
                while(set.contains(sum)&&sum>0){
                    if(beef>0){//汉堡数量相同且有牛肉汉堡，则牛肉的减少
                        sum--;
                        beef--;
                    }
                    else{
                        sum--;//否则减少的是鸡肉，总数对应减少
                    }
                }
                num+=beef;//累计牛肉数量
                set.add(sum);
            }
        }
        return num;
    }
}

复杂度：

• 时间复杂度：$O(nlogn)O(nlogn)$,每次出队元素的时间复杂度为$O(logn)O(logn)$，每个元素至少访问一遍，因此时间复杂度为$O(nlogn)O(nlogn)$

• 空间复杂度：$O(n)O(n)$,哈希表和队列的元素数量不超过n

方法二：自定义排序+贪心

基于方法一，我们可以用自定义排序替换优先级队列，思路基本相同

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型
     */
    public class Ham{
        int chicken,beef;
        int sum;
        Ham(int chicken,int beef){
            this.chicken=chicken;
            this.beef=beef;
            this.sum=this.chicken+this.beef;
        }
    }
    public long EatingHamburger (int n, int[] a, int[] b) {
        // write code here
        Set<Integer>set=new HashSet<>();
        Ham[]hams=new Ham[n];
        for(int i=0;i<n;i++){
            hams[i]=new Ham(a[i],b[i]);
        }
        Arrays.sort(hams,new Comparator<Ham>(){
            public int compare(Ham x,Ham y){
                return y.sum-x.sum;
            }
        });//根据每天汉堡数量自定义递减排序
        int num=0;//牛肉数量
        for(int i=0;i<n;i++){
            Ham curr=hams[i];
            int sum=curr.sum;
            int beef=curr.beef;
            if(!set.contains(sum)){//先保证汉堡数量最多且不重复
                set.add(sum);
                num+=beef;
            }
            else{
                while(set.contains(sum)&&sum>0){
                    if(beef>0){//汉堡数量相同且有牛肉汉堡，则牛肉的减少
                        sum--;
                        beef--;
                    }
                    else{
                        sum--;//否则减少的是鸡肉，总数对应减少
                    }
                }
                num+=beef;//累计牛肉数量
                set.add(sum);
            }
        }
        return num;
    }
}

复杂度:

• 时间复杂度：$O(nlogn)O(nlogn)$,自定义排序的时间复杂度为$O(nlogn)O(nlogn)$
• 空间复杂度：$O(n)O(n)$,哈希表和数组的元素数量不超过n