题解 | #吃汉堡#

吃汉堡

https://www.nowcoder.com/practice/09a480cee1364e4180fa304d2b9c78c7

描述

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

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

示例1

输入：

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

复制

返回值：

复制

说明：

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

备注：

1\leq n,a[i],b[i] \leq 10^51≤n,a[i],b[i]≤105

解题思路：

1、明确题意，吃的汉堡尽可能多，每天不能重复，尽量少吃牛肉汉堡；

2、吃的汉堡尽可能多：a[i]+b[i]是每天最多能吃的汉堡个数；

3、每天不能重复：使用泛型函数find可以找到第i天如果将汉堡全部吃完的话会不会有重复；

 while (find(sum.begin(), sum.end(), tmp) != sum.end()) {
    int index = find(sum.begin(), sum.end(), tmp) - sum.begin();
    if (b[i] > b[index] && b[i] > 0) {

4、尽量少吃牛肉汉堡：如果有重复的话就从牛肉汉堡吃的最多的那天中减掉一个，同时刷新牛肉汉堡数组和汉堡总和；

5、需要注意，如果将重复天数中牛肉汉堡都减完了还是有重复的话，就需要从当天中减去鸡肉汉堡。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型
     */
    long long EatingHamburger(int n, vector<int>& a, vector<int>& b) {
        // write code here
        vector<long long> sum(n , 0);
        long long res = 0;
        for (int i = 0; i < n; i++) {
            long long tmp = a[i] + b[i];
            while (find(sum.begin(), sum.end(), tmp) != sum.end()) { //循环判断直至tmp与已有数组没有重复
                int index = find(sum.begin(), sum.end(), tmp) - sum.begin();
                if (b[i] > b[index] && b[i] > 0) { // 重复数据中哪天吃的牛肉汉堡多久从哪天减1
                    b[i]--;
                    tmp--;
                } else if (b[index] > 0){
                    b[index]--;
                    sum[index]--;
                    res--;
                } else { // 若重复天中均没有牛肉汉堡了，那么需要从鸡肉汉堡中减1
                    a[i]--;
                    tmp--;
                }
                
            } 
            res += b[i];
            sum[i] = tmp;
        }
        return res;

    }
};