Python程序：查找我们可以使最多的人快乐

假设我们有一个客户列表customers和另一个情绪列表mood，这两个列表长度相同，我们还有一个整数k。现在，在每一分钟i，customers[i]数量的人来到商店，当mood[i] = 1时，表示顾客很高兴，当mood[i] = 0时，表示他们不高兴。我们可以将大小为k的mood子列表设置为1，最后我们必须找到我们可以使最多的人快乐的数量。

因此，如果输入类似于customers = [2, 3, 6, 6, 3] mood = [1, 1, 0, 0, 0] k = 2，则输出将为17，因为如果我们将mood[2]和mood[3]设置为1，则总情绪将为2 + 3 + 6 + 6 = 17个顾客感到高兴。

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

• n := mood的大小
• a := 一个大小为(n + 1)的列表，并用0填充
• s := 0
• 对于范围从0到n - 1的i，执行以下操作：
  • a[i + 1] := a[i]
  • 如果mood[i]不为零，则：
    • s := s + customers[i]
  • 否则：
    • a[i + 1] := a[i + 1] + customers[i]
• d := 0
• 对于范围从k到n的i，执行以下操作：
  • d := d和(a[i] - a[i - k])的最大值
• 返回s + d

示例

让我们看看以下实现以更好地理解：

def solve(customers, mood, k):
   n = len(mood)
   a = [0] * (n + 1)
   s = 0
   for i in range(n):
      a[i + 1] = a[i]
      if mood[i]:
         s += customers[i]
      else:
         a[i + 1] += customers[i]
   d = 0
   for i in range(k, n + 1):
      d = max(d, a[i] - a[i - k])
   return s + d

customers = [2, 3, 6, 6, 3]
mood = [1, 1, 0, 0, 0]
k = 2
print(solve(customers, mood, k))

输入

[2, 3, 6, 6, 3], [1, 1, 0, 0, 0], 2

输出

17

Arnab Chakraborty

更新于：2021年10月14日

453 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始