题意整理：

题目给出两个数组a和b。对于一个i，$a\left[i\right]a[i]$a[i]表示第i天的鸡肉汉堡数量，$b\left[i\right]b[i]$b[i]表示第i天的牛肉汉堡数量。要求计算出在每天吃的汉堡总数不同的情况下，且吃到尽量多的汉堡（两种汉堡之和）的情况下尽量少吃牛肉汉堡，在以上前提下最少需要吃的牛肉汉堡数量。

抽象的说，就是求出满足（优先级从上到下）

$a\left[i\right]+b\left[i\right]\ne a\left[j\right]+b\left[j\right],i\ne ja[i]+b[i]\; \backslash neq\; a[j]+b[j]\; ,i\backslash neq\; j$a[i]+b[i]​=a[j]+b[j],i​=j

${\sum }_{i=0}^{n-1}\left(a\right[i]+b[i\left]\right)\to max\backslash sum\_\{i=0\}^\{n-1\}\; \{(a[i]+b[i])\}\; \to max$∑i=0n−1​(a[i]+b[i])→max

${\sum }_{i=0}^{n-1}b\left[i\right]\to min\backslash sum\_\{i=0\}^\{n-1\}\; \{b[i]\}\; \to min$∑i=0n−1​b[i]→min

时的${\sum }_{i=0}^{n-1}b\left[i\right]\backslash sum\_\{i=0\}^\{n-1\}\; \{b[i]\}$∑i=0n−1​b[i]

方法一：排序+优先队列

核心思想：

题目要求在满足每天吃的汉堡数不同的情况下，满足两个极限条件（最多及最少）时的情况下所吃的牛肉汉堡,一般这种极限问题,可以考虑采用贪心的思想.

首先可以将所有天数的两种汉堡数构成的二元组加入优先队列进行排序,排序依据是:首先按汉堡总数排序,之后按鸡肉汉堡数排序.排序完成后,我们贪心地依次取出队列首部元素(既总数最多或在存在多个总数最多的情况下鸡肉汉堡最多的),然后判断与上次吃的总汉堡数的关系,如果小于上次吃的则直接吃掉全部并记录,如果比上次吃的多或相等则需要逐渐抛弃一些汉堡直到比上次吃的少,抛弃汉堡的顺序为先抛弃牛肉汉堡,牛肉汉堡数为0后开始抛弃鸡肉汉堡,下面简单证明这种策略不会导致错误答案.

1).当此次的总汉堡数少于上次的总汉堡数,显然全部吃完是最优的

2).当此次的总汉堡数等于上次的总汉堡数,此时不能够吃这么多否则会畅神冲突,这时可能有两种情况,第一则是减少上一轮吃的总汉堡数,第二种则是减少此次吃的总汉堡数,但由于总汉堡数相同情况下是按照鸡肉汉堡数排序,所以减少此次吃的总汉堡数不会差于减少上次吃的总汉堡数,而可能优于减少上次吃的总汉堡数(因为减少此次吃的总汉堡数可以更多的抛弃牛肉汉堡)

3).此次的总汉堡数多于上次吃的总汉堡数.由于存在不能够吃一样的汉堡数,所以这种情况是存在的.这次采取的策略是不断减少此次的汉堡数直到比上一次少,而不是直接吃下所有汉堡,因为如果直接吃下汉堡必然造成冲突,否则导出矛盾. 设当前汉堡数为m,上一次吃的汉堡数为p,$m>pm>p$m>p,此时如果能够吃比p更多的汉堡数q,则说明之前未出现过吃q个汉堡的情况,但由于取出汉堡是按总汉堡数排序,总汉堡数相同按鸡肉堡数排序,所以在取出当前元素的上一个元素同样能够取得q个汉堡而不引起冲突,这与之前描述的策略产生冲突,不可能存在,所以只能够取得比上一次更少的汉堡总数.

核心代码：

class Solution {
public:
    struct cmp {
        bool operator()(vector<int>& r1, vector<int>& r2) {
            //自定义排序
            return r1[0] + r1[1] == r2[0] + r2[1] ? r1[0] < r2[0] : r1[0] + r1[1] < r2[0] + r2[1];
        }
    };
    
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        priority_queue<vector<int>, vector<vector<int>>, cmp> q;
        for(int i = 0; i < n; ++i) {
            q.push({a[i], b[i]});//加入优先队列
        }
        long long ans = 0;
        int p = INT_MAX;
        while(!q.empty()) {
            //不断取出汉堡吃掉
            vector<int> it = q.top();
            q.pop();
            if(it[0] + it[1] < p) {
                //比上一次吃的少，全部吃完即可
                ans += it[1];
                p = it[0] + it[1];
            } else if(it[0] + it[1] == p) {
                //此时需要少吃一个，尽量少吃鸡肉堡
                ans += it[1] == 0 ? 0 : it[1] - 1;
                --p;
            } else {
                //此时既it[0] + it[1] > p,需要至多吃p-1个并少吃鸡肉堡
                ans += it[0] < (p - 1) ? p - 1 - it[0] : 0;
                --p;
            }
            if(p == 0) break;//不可能继续吃
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：$O\left(nlogn\right)O(nlogn)$O(nlogn)。每个元素被放入和取出最多一次,而优先队列原理为堆,其排序消耗为$O\left(nlogn\right)O(nlogn)$O(nlogn)

空间复杂度：$O\left(n\right)O(n)$O(n),既为优先队列的开销

方法二：排序+数组

核心思想：

思路与方法一相同,不过可以通过使用临时数组直接排序而不是借助优先队列,其他部分相同.

核心代码：

class Solution {
public:
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        vector<vector<int>> res(n, vector<int>(2));
        for(int i = 0; i < n; ++i) {
            //构造数组
            res[i][0] = a[i];
            res[i][1] = b[i];
        }
        //按汉堡总数排序，总数相同按鸡肉堡数量排序
        sort(res.begin(), res.end(), [&](vector<int>& r1, vector<int>& r2) {
            return r1[0] + r1[1] == r2[0] + r2[1] ? r1[0] > r2[0] : r1[0] + r1[1] > r2[0] + r2[1];
        });
        int p = INT_MAX;//记录上一次吃的汉堡总数
        long long ans = 0;
        for(vector<int>& it : res) {
            if(it[0] + it[1] < p) {
                //比上一次吃的少，全部吃完即可
                ans += it[1];
                p = it[0] + it[1];
            } else if(it[0] + it[1] == p) {
                //此时需要少吃一个，尽量少吃鸡肉堡
                ans += it[1] == 0 ? 0 : it[1] - 1;
                --p;
            } else {
                //此时既it[0] + it[1] > p,需要至多吃p-1个并少吃鸡肉堡
                ans += it[0] < (p - 1) ? p - 1 - it[0] : 0;
                --p;
            }
            if(p == 0) break;//不可能继续吃
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：$O\left(nlogn\right)O(nlogn)$O(nlogn)。既为sort排序的开销

空间复杂度：$O\left(n\right)O(n)$O(n),既临时构造的辅助数组的大小