leetcode 1599 (也是208场周赛第2题）

经营摩天轮的最大利润

1. 先看执行效率，我觉得有假。

   
   Screenshot from 2020-09-29 21-06-39.png

2. 思路见注释。

class Solution:
    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:
        """
        思路：
        # 稍微简化一下题意，就是如何把 c = [8, 3]转化为   c = [4, 4, 3]
        # 思路就是每次取4， 如果大于4， 那么就把多余的部分加到下一个头上。
        # 一直到最后，看看最后一个值是否还是大于4，然后不断削减。
        # c = [4, 3+4] = [4, 4, 3]

        # 而我当时的想法是，用一个remain来保存大于4的部分，结果路走窄了。。。
        """

        max_profit = float("-inf")
        running_times = 1
        profit = 0
        dic = {}    # dic = {running_times: profit}

        n = len(customers)
        
        i = 0
        profit = 0
        while i < n-1:  # 无法取到最后一位。
            if customers[i] > 4:
                customers[i+1] += customers[i] - 4
                profit += 4 * boardingCost - runningCost
            else:
                profit += customers[i]*boardingCost - runningCost
            
            dic[running_times] = profit

            i += 1
            running_times += 1

        while customers[i]:
            if customers[i] > 4:
                customers[i] -= 4
                profit += 4 * boardingCost - runningCost 
                dic[running_times] = profit
            else:
                profit += customers[i]*boardingCost - runningCost
                dic[running_times] = profit
                break

            running_times += 1

        # print(dic)  # {1: 14, 2: 28, 3: 37}
        ret = sorted(dic.items(), key=lambda x: [x[1], -x[0]]).pop()
        if ret[1] > 0:
            return ret[0]
        else:
            return -1

        """
        134 / 136 个通过测试用例
        [10,10,1,0,0]
        4
        4
        这个运行的实际结果是  {1: 12, 2: 24, 3: 36, 4: 48, 5: 60, 6: 60}
        也就是说运行的结果是正确的，但是最终排序取值的时候出错了。
        解决办法：
        1. 改为动态赋值，但是我觉得对整体思路而言显得有点杂乱。
        2. 修改排序规则。key=lambda x: [x[1], -x[0]]

        """