题解 | #吃汉堡#

一.题目描述
NC563吃汉堡
牛妹爱吃汉堡包，她觉得鸡肉汉堡包比牛肉汉堡包好吃。牛妹参加了一个活动，每天商家会给牛妹发a[i]个鸡肉汉堡包,b[i]个牛肉汉堡包，持续n天。牛妹想吃尽可能多的汉堡，而每天吃的汉堡总个数都不相同，并且尽可能少吃牛肉汉堡包。返回在尽可能多吃汉堡包的条件下，n天下来至少需要吃牛肉汉堡包的数量。
图片说明
二.算法(贪心)
理解题目意思后我们发现应该采用贪心的思路，在开始贪心的时候，我们首先就要对每天的汉堡总数进行排序，进而保证贪心可以顺利的进行下去。对于汉堡总数不同的情况，对汉堡总数量进行标记，并且吃完牛肉汉堡；对于汉堡个数相同的情况，我们就需要从汉堡总数相同的数量往前依次遍历，找到最大的汉堡总数数量，然后判断是否可以少吃牛肉汉堡，对每一次结果依次进行累计，最后得到返回值。下面是完整代码：

const int N=1e4+5;
class Solution {
public:
    struct node{
        int x, y;
        bool friend operator <(node& a, node& b) {
            return a.x > b.x;
        }
    }num[N];
    unordered_map<int,int>mp;
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        for(int i=0;i<n;i++){
            num[i].x=a[i]+b[i];
            num[i].y=b[i];
        }
        //基于贪心按照汉堡总数对汉堡个数进行排序
        sort(num,num+n);
        int sum=0,k=0;
        for(int i=0;i<n;i++){
            if(!mp[num[i].x]){
                //汉堡总数还没有被访问过
                sum+=num[i].y;
                mp[num[i].x]=1;
                k=0;
            } else {
                //汉堡总数已经被访问过
                while(mp[num[i].x-k]) k++;
                //往前去寻找没有被访问过的汉堡总数
                sum+=max(num[i].y-k,0);
                mp[num[i].x-k]=1;
            }
        }
        return sum;
    }
};

时间复杂度： $O(nlogn)$ 只需要对数组进行一次遍历并且排序
空间复杂度： $O(n)$ 需要开辟空间存储牛肉汉堡和鸡肉汉堡个数
优缺点：贪心思想要注意细节，但是代码简单便于实现
三.算法(排序)
首先我们要利用结构体对每天汉堡的总数和鸡肉汉堡的数量进行记录，然后对结构体按照汉堡总数进行排序，使
吃到可以最多的汉堡。对于汉堡总数相同，但是分配不同的情况，我们需要对汉堡总数相同情况下的鸡肉汉堡排序，使得吃的汉堡总数越多的情况下吃的鸡肉汉堡越多，自然而然此时吃的牛肉汉堡的数量就越来约少了。只需要每次取出排序后最大的鸡肉汉堡就行了，达到吃最多的汉堡总数，对于牛肉汉堡的数量我们不需要管。
图片说明 (该图片来自于牛客)
下面是完整代码：

class Solution {
public:
    struct node{
        int x, y;
        bool friend operator <(node& a, node& b) {
            return a.x>b.x;
        }
    };
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        vector<node> num(n);
        for(int i=0;i<n;i++){
            num[i].x=a[i]+b[i];
            num[i].y=a[i];
        }
        sort(num.begin(),num.end());//利用汉堡总数进行排序
        vector<int> q;
        long long ans=0;//返回最少需要吃牛肉汉堡的数量
        int cnt=0;//利用下标cnt查找汉堡总数相同的天数
        for(int i=num[0].x;i>= 0;i--){
            while(cnt<n&&num[cnt].x==i){
                q.push_back(num[cnt].y);
                cnt++;
            }
            //按照鸡肉汉堡的数量进行排序
            sort(q.begin(),q.end()); 
            if(q.size()!=0){
                //求出要吃的牛肉汉堡数量
                ans+=max(i-q.back(), 0);
                q.pop_back();
            }
        }
        return ans;
    }
};

时间复杂度： $O(n^{2}logn)$ 需要进行遍历并且还要进行排序，所以复杂度达到了 $O(n^{2}logn)$
空间复杂度： $O(n)$ 需要额外空间对鸡肉汉堡数量进行排序
优缺点：时间复杂度高，但是思路简单便于实现