题解 | #吃汉堡#

思路：

题目的主要信息：

• a数组表示每天的鸡肉汉堡数，b数组表示每天的牛肉汉堡数
• 一共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> v(n);
        for(int i = 0; i < n; i++){ //录入总汉堡数和牛肉汉堡数
            v[i].x = a[i] + b[i];
            v[i].y = a[i];
        }
        sort(v.begin(), v.end());  //总汉堡排序
        vector<int> temp;
        long long res = 0;
        for(int i = v[0].x, j = 0; i >= 0; i--){ //i为某天吃的总汉堡数
            while(j < n && v[j].x == i){  //找到后面相同的
                temp.push_back(v[j].y);  //牛肉汉堡入队列，优先牛肉少排序
                j++;
            }
            sort(temp.begin(), temp.end()); //鸡肉汉堡数递减排序
            if(temp.size() != 0){
                res += max(i - temp[temp.size() - 1], 0); //每次取出最大的鸡肉汉堡
                temp.pop_back();
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况全部总汉堡数都相等，每次sort排序为
• 空间复杂度：，两个辅助的有序列表

方法二：有序列表+优先队列
具体做法：
对于第一个有序列表我们可以继续用方法一的形式，对于第二个有序列表，我们可以使用优先队列避免每次排序。

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> v(n);
        for(int i = 0; i < n; i++){ //录入总汉堡数和牛肉汉堡数
            v[i].x = a[i] + b[i];
            v[i].y = a[i];
        }
        sort(v.begin(), v.end());  //总汉堡递减排序
        priority_queue<int> pq;
        long long res = 0;
        for(int i = v[0].x, j = 0; i >= 0; i--){ //i为某天吃的总汉堡数
            while(j < n && v[j].x == i){
                pq.push(v[j].y);  //鸡肉汉堡入队列，优先鸡肉多的排序在前
                j++;
            }
            if(!pq.empty()){
                res += max(i - pq.top(), 0);//每次取出最大的鸡肉汉堡
                pq.pop();
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，优先队列加入一个元素为
• 空间复杂度：，辅助数组和优先队列