吃汉堡题解

这道题首先我们可以发现可以吃掉的最大汉堡数量是一定的。那么我们从大到小枚举吃多少汉堡，用一个集合来维护当前可以被吃掉的汉堡组合，我们会发现，吃3个汉堡包的集合一定是吃2个汉堡包的集合的子集。那么我们从大到小枚举，每次只需要选取当前集合中鸡肉汉堡包最多的来吃就好了。选取最多的我们用优先队列来维护。时间复杂度O(nlogn)，空间复杂度O(n)。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @param b int整型一维数组 
     * @param bLen int b数组长度
     * @return long长整型
     */
    struct node{
        int x,y;
        bool friend operator <(node a,node b) {
            return a.x+a.y>b.x+b.y;
        }
    }A[100001];
    long long EatingHamburger(int n, int* a, int aLen, int* b, int bLen) {
        // write code here
        for(int i=1;i<=n;i++) A[i].x=a[i-1],A[i].y=b[i-1];
        sort(A+1,A+1+n);
        int pos=1;
        long long ans=0;
        priority_queue<int>q;
        for(int i=200000;i;i--) {
            while(A[pos].x+A[pos].y>=i&&pos<=n) q.push(A[pos].x),pos++;
            if(!q.empty()) {
                ans+=max(0,i-q.top());
                q.pop();
            }
        }
        return ans;
    }
};