吃汉堡

[编程题]吃汉堡

热度指数：559 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹爱吃汉堡包，她觉得鸡肉汉堡包比牛肉汉堡包好吃。牛妹参加了一个活动，每天商家会给牛妹发a[i]个鸡肉汉堡包,b[i]个牛肉汉堡包，持续n天。牛妹想吃尽可能多的汉堡，而每天吃的汉堡总个数都不相同，并且尽可能少吃牛肉汉堡包。

返回在尽可能多吃汉堡包的条件下，n天下来至少需要吃牛肉汉堡包的数量。

示例1

输入

2,[1,2],[2,1]

输出

说明

牛妹两天吃的汉堡包总量为2+3。牛妹选择第一天吃1个鸡肉1个牛肉，第二天吃2个鸡肉1个牛肉的。
可以证明，这样选择是最优的（共吃了5个汉堡，且每天吃的数量都不同）

备注:

算法知识视频讲解

C/C++

nbgao

struct P{
    int s, a;
};

bool cmp(P p1, P p2){
    return p1.s > p2.s;
}

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @param b int整型一维数组 
     * @param bLen int b数组长度
     * @return long长整型
     */
    long long EatingHamburger(int n, int* a, int aLen, int* b, int bLen) {
        long long sum = 0;
        P p[n];
        for(int i=0;i<n;i++)
            p[i] = P{a[i]+b[i], a[i]};
        sort(p, p+n, cmp);
        priority_queue<int> q;
        for(int i=p[0].s,j=0;i>=0;i--){
            while(j<n && p[j].s>=i){
                q.push(p[j].a);
                j++;
            }
            if(!q.empty()){
                sum += max(i-q.top(), 0);
                q.pop();
            }
        }
        return sum;
    }
};

发表于 2020-07-23 01:27:42 回复(1)

牛客952005053号

class Solution:
def EatingHamburger(self , n , a , b ):
# write code here
pairs = [(a[i] + b[i], b[i]) for i in range(n)]
# 总数降序：尽量多吃；牛肉升序：尽量少吃
pairs.sort(key = lambda x : (-x[0], x[1]))
usedNum = set()
res = 0
for pair in pairs:
acc, beef = pair[0], pair[1]
while acc in usedNum:
acc -= 1
if beef > 0:
beef -= 1
usedNum.add(acc)
res += beef
return res

发表于 2022-07-26 21:50:51 回复(0)

henry_dai

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @return long长整型
     */
    class HamDay implements Comparable{
        int jirou;
        int niurou;
        int sum;
        HamDay(int a,int b)
        {
            jirou=a;
            niurou=b;
            sum=a+b;
        }

        @Override
        public int compareTo(Object o) {
            HamDay h = (HamDay) o;
            if(this.sum>h.sum)
            {
                return -1;
            }
            else if(this.sum<h.sum)
            {
                return 1;
            }
            else
            {
                if(this.jirou>h.jirou)
                    return -1;
                else
                    return 1;
            }
        }
    }
    public long EatingHamburger (int n, int[] a, int[] b) {
        // write code here
        PriorityQueue<HamDay> pq = new PriorityQueue<>();
        HashSet<Integer> set = new HashSet<>();
        long count = 0;
        for(int i=0;i<n;i++)
        {
            pq.add(new HamDay(a[i],b[i]));
        }
        while(pq.size()!=0)
        {
            HamDay temp = pq.remove();
            if(!set.contains(temp.sum))
            {
                count+=temp.niurou;
                set.add(temp.sum);
            }
            else
            {
                int num = temp.sum;
                int niu = temp.niurou;
                while(set.contains(num)&&num>0)
                {
                    if(niu!=0)
                    {
                        niu--;
                        num--;
                    }
                    else
                    {
                        num--;
                    }
                }
                count+=niu;
                set.add(num);
            }

        }
        return count;
    }
}

发表于 2021-04-26 11:24:23 回复(0)