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

通过万岁！！！

• 题目：就是一个摩天轮，一共有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已经是越界的了，所以这里要减1i--;// 都上会盈利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;}
}

• 总结：题目不是特别难，我最开始主要是被我说的迷惑的地方绕进去了。