Python 中的脾气暴躁的书店老板

pythonserver side programmingprogramming更新于 2025/11/14 16:12:17

假设书店老板开店的时间为顾客列表条目数分钟。每分钟，一定数量的顾客(customers[i])进入商店，之后所有这些顾客都会在该分钟结束后离开。在某些分钟，店主会脾气暴躁。现在，如果店主在第 i 分钟脾气暴躁，则 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板脾气暴躁时，那一分钟的顾客会不高兴，否则他们会高兴。书店老板知道一种让自己连续 X 分钟不脾气暴躁的技巧。这种技巧不能使用多次。我们必须找到全天可以高兴的最大顾客数量。因此，如果输入如下:customers = [1,0,1,2,1,1,7,5] and grumpy = [0,1,0,1,0,1] 且 X = 3，则输出将为 16。这是因为店主在最后三分钟内不会脾气暴躁。因此，满意顾客的最大数量为 1 + 1 + 1 + 1 + 7 + 5 = 16

为了解决这个问题，我们将遵循以下步骤 −

set i := 0, j := 0, sums := empty list and temp := 0
while j – i + 1 < X
- 如果 grumpy[j] 为 1，则 temp := temp + customers[j]
- 将 j 增加 1
将列表 [temp, i, j] 插入到 sums 数组中
将 i 和 j 增加 1
当 j < 客户列表的长度
- 如果 grumpy[i - 1] 为 1，则 temp := temp – customers[i - 1]
- 如果 grumpy[j] 为 1，则 temp := temp + customer[j]
- 将列表 [temp, i, j] 插入 sums 数组
- 将 i 和 j 增加 1
sums := 根据内部列表的第一个元素对 sums 数组进行排序
index1 := sums 中最后一个列表的第二个元素，index2 := sums 中最后一个列表的第三个元素，
对于 index1 到 index2 范围内的 i，设置 grumpy[i] := 0
ans := 0
对于 0 到 customers 长度范围内的 i
- 如果 grumpy[i] 为 0，则 ans := ans + customers[i]
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class Solution(object):
   def maxSatisfied(self, customers, grumpy, X):
      i = 0
      j = 0
      sums = []
      temp = 0
      while j-i+1<X:
         if grumpy[j]:
            temp+=customers[j]
         j+=1
      sums.append([temp,i,j])
      i+=1
      j+=1
      while j<len(customers):
         if grumpy[i-1]:
            temp-=customers[i-1]
         if grumpy[j]:
            temp+=customers[j]
         sums.append([temp,i,j])
         i+=1
         j+=1
      sums =sorted(sums,key = lambda v : v[0])
      index1 = sums[-1][1]
      index2 = sums[-1][2]
      for i in range(index1,index2+1):
         grumpy[i] = 0
      ans = 0
      for i in range(len(customers)):
         if not grumpy[i]:
            ans+=customers[i]
      return ans
ob = Solution()
print(ob.maxSatisfied([1,0,1,2,1,1,7,5],[0,1,0,1,0,1,0,1],3))