NC563 题解 | #吃汉堡#

题意分析

一个人需要吃n天的汉堡，每天会给两种汉堡及其数量，分别为牛肉汉堡和鸡肉汉堡，对于吃这n天的汉堡，需要满足如下条件
- 每天吃的汉堡的数量都不一样。
- 在吃的总的汉堡的数量最多的前提下，吃尽可能少的牛肉汉堡。
- 注意每天给的汉堡不一定要吃完

思路分析

首先，这个题目是一个贪心的思路，我们来看一下怎样的贪心的方法。我们先来看一下优先级，首先要确保总的数量最多，然后就是相同的数量下要尽可能使得其中的牛肉汉堡的数量少。那么我们肯定先满足数量最多，我们需要找到数量最多的是哪些天。这一点我们就可以使用结构体排序或者优先队列进行处理。
处理完之后，我们观察到题目给出汉堡的总的数量最多也就是2e5左右，那么我们就可以从一天吃的最多的汉堡数量进行枚举，看哪些天给的汉堡满足这个数量，然后选择这些天里面的鸡肉汉堡数量最多的那天,这里我们使用大根堆来维护。（由于汉堡的总数是一样的，选择鸡肉汉堡数量最多那么就间接地让牛肉汉堡的数量尽可能少）。然后继续向下枚举每天吃的汉堡的数量。进行同样的处理。最后就得到了最优的结果了。
这里我们用下面一个简单的例子来帮助大家更好地理解

alt

解法一双优先队列

首先，我们定义一个结构体存储每天总的汉堡的数量和我们的每天的鸡肉汉堡的数量，然后重载运算符，将数据放到优先队列里面，这样我们就找到了就可以找到枚举的上限。然后将满足当前汉堡的天数放到我们最后优先队列里面。
代码如下
- 利用了两个优先队列进行处理，优先队列每次对堆进行调整的时候是 $O (l o g n)$ ，所以总的时间复杂度为 $O (n l o g n)$
- 使用队列进行处理，将n天的汉堡情况放到队列里面，空间复杂度为 $O (n l o g n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型
     */
    typedef long long ll;
    struct node{
        int sum; // 总的汉堡的个数
        int num; // 其中牛肉堡的个数
        // 重载函数，让汉堡总和大的在前面
        friend bool operator < (const node &a,const node &b){
            return a.sum < b.sum;
        }
    };
    priority_queue<node> q1;
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        // write code here
        for(int i=0;i<n;i++){
            q1.push(node{a[i]+b[i],a[i]});
        }
        
        ll ans=0;
        
        priority_queue<int> q;
        // 从数量最多的开始进行枚举
        for(int i=q1.top().sum;i;i--){
            // 找到那些天可以满足可以吃到i个汉堡，将吃的鸡肉汉堡的个数放到队列里面
            while(!q1.empty()&&q1.top().sum>=i){
                q.push(q1.top().num);
                q1.pop();
            }
            if(!q.empty()){
                // 找到队列里面吃的鸡肉汉堡最多是多少，在总的汉堡个数相同的情况下就间接让吃的牛肉汉堡最少
                ans+=max(0,i-q.top());
                q.pop();
            }
        }
        
        
        return ans;
    }
};

解法二数组+优先队列

第二种解法其实和第一种解法的思路是类似的，只是我们使用的是结构体数组来存储n天的汉堡的情况，我们知道，一旦对n天的汉堡的情况进行排序之后，后续执行的操作其实就是出堆的操作，所以我们只需要利用结构体存储，然后对结构体进行排序，后续按照顺序依次取用结构体里面的数据即可。过程中我们维护一个指针指向当前结构体数组指向的位置。其余的过程还是和之前的一样。
代码如下
- 过程中利用了结构体排序，然后我们使用了优先队列来优化处理，总的时间复杂度为 $O (n l o g n)$
- 我们使用了结构体数组存储n天的汉堡的情况，同时使用了优先队列执行对应的出栈和入栈的操作，总的空间复杂度为 $O (n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型
     */
    typedef long long ll;
    struct node{
        int sum; // 总的汉堡的个数
        int num; // 其中牛肉堡的个数
        // 让汉堡总和大的在前面
        bool operator < (const node &b){
            return sum>b.sum;
        }
    }Node[100010];
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        // write code here
        for(int i=0;i<n;i++){
            Node[i].sum=a[i]+b[i];
            Node[i].num=a[i];
        }
        
        ll ans=0;
        // 按照总的汉堡的个数进行排序
        sort(Node,Node+n);
        
        priority_queue<int> q;
        // 从数量最多的开始进行枚举
        for(int i=Node[0].sum,j=0;i;i--){
            // 找到那些天可以满足可以吃到i个汉堡，将吃的鸡肉汉堡的个数放到队列里面
            while(j<n&&Node[j].sum>=i){
                q.push(Node[j].num);
                j++;
            }
            if(!q.empty()){
                // 找到队列里面吃的鸡肉汉堡最多是多少，在总的汉堡个数相同的情况下就间接让吃的牛肉汉堡最少
                ans+=(i-q.top());
                q.pop();
            }
        }
        
        
        return ans;
    }
};

NC563 题解 | #吃汉堡#

NC563 题解 | #吃汉堡#

题意分析

思路分析

解法一 双优先队列

解法二 数组+优先队列

解法一双优先队列

解法二数组+优先队列