LeetCode——1599. 经营摩天轮的最大利润

发布时间:2024年01月01日

通过万岁!!!

  • 题目:就是一个摩天轮,一共有4个仓位,一个仓位中最多可以做4个人。然后每次上一个人boardingCost钱,但是我们转动1/4圈,需要的成本是runningCost。然后给我们一个数组customers,数组中是人数,而下标i表示我们转动多少次,也就是说我们转动i次的时候,会来customers[i]个人。如果坐满了,那么多余的人只能等待下一批,也就是i+1的时候,而且这是时候也会来customers[i+1]个人。但是题目中有个地方有点迷惑人,假设我们在某个位置决定停止营业,则需要将上面所有的人都送下来才行。问我们第几次转动的盈利是最大的。
  • 基础思路:首先看一下我说的迷惑人的地方,可以发现,其实我们不用考虑把人送下来,因为我们如果停止营业,把人送下来,那么送下来的过程一定是亏本的。那么盈利最大值的肯定在此之前。然后再说一下我们的思路,就是模拟这个过程就好了。首先我们需要遍历数组,并且需要记录一下剩余的人数,如果两者之和大于4,则按照上4人的盈利标准来。否则按照现有的人数来计算。然后跟max的利润进行比较就好了。当我们遍历完数组之后,我们还需要遍历剩余的人数,将这些人安排好。在此过程中我们就可以找到最大值了。
  • 优化思路:其实在遍历完数组以后,针对剩余人数的计算可以进行优化的。如果上4人可以盈利的话,那么我们将剩余人数/4*每次的盈利,然后在针对不足4人的情况继续考虑。
  • 技巧:模拟

java代码——基础

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        int maxcurrProfit = Integer.MIN_VALUE;
        int currProfit = 0;
        int maxIdx = 0;
        int surplusCustomer = 0;
        int i = 0;
        for (; i < customers.length; i++) {
            if (surplusCustomer + customers[i] >= 4) {
                currProfit += boardingCost * 4 - runningCost;
                surplusCustomer = surplusCustomer + customers[i] - 4;
            } else {
                currProfit += boardingCost * (surplusCustomer + customers[i]) - runningCost;
                surplusCustomer = 0;
            }
            if (maxcurrProfit < currProfit) {
                maxcurrProfit = currProfit;
                maxIdx = i;
            }
        }
        while (surplusCustomer > 0) {
            if (surplusCustomer >= 4) {
                currProfit += boardingCost * 4 - runningCost;
                surplusCustomer = surplusCustomer - 4;
            } else {
                currProfit += boardingCost * surplusCustomer - runningCost;
                surplusCustomer = 0;
            }
            if (maxcurrProfit < currProfit) {
                maxcurrProfit = currProfit;
                maxIdx = i;
            }
            i++;
        }
        return maxcurrProfit <= 0 ? -1 : maxIdx + 1;
    }
}

java代码——优化

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        int maxProfit = Integer.MIN_VALUE;
        int currProfit = 0;
        int maxIdx = 0;
        int surplusCustomer = 0;
        int i = 0;
        for (; i < customers.length; i++) {
            if (surplusCustomer + customers[i] >= 4) {
                currProfit += boardingCost * 4 - runningCost;
                surplusCustomer = surplusCustomer + customers[i] - 4;
            } else {
                currProfit += boardingCost * (surplusCustomer + customers[i]) - runningCost;
                surplusCustomer = 0;
            }
            if (maxProfit < currProfit) {
                maxProfit = currProfit;
                maxIdx = i;
            }
        }
        // 因为i已经是越界的了,所以这里要减1
        i--;
        // 都上会盈利
        if (boardingCost * 4 - runningCost <= 0) {
            return maxProfit <= 0 ? -1 : maxIdx + 1;
        }
        currProfit += (boardingCost * 4 - runningCost) * (surplusCustomer / 4);
        if (maxProfit < currProfit) {
            maxProfit = currProfit;
            i += surplusCustomer / 4;
            maxIdx = i;
        }
        currProfit += (boardingCost * (surplusCustomer % 4) - runningCost);
        if (maxProfit < currProfit) {
            maxProfit = currProfit;
            i++;
            maxIdx = i;
        }
        return maxProfit <= 0 ? -1 : maxIdx + 1;
    }
}
  • 总结:题目不是特别难,我最开始主要是被我说的迷惑的地方绕进去了。
文章来源:https://blog.csdn.net/qq_39056803/article/details/135330410
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。