Pythonで幸せにできる最大人数を見つけるためのプログラム

リストの顧客と別のリストのムードがあり、これら2つが同じ長さであり、別の整数kもあるとします。これで、毎分iで、customers [i]の人数が来店し、mood [i] =1の場合は顧客が満足し、mood [i]=0の場合は悲しいことを示します。気分のサイズkのサブリストを1に設定できます。最後に、幸せにできる最大人数を見つける必要があります。

したがって、入力がcustomers =[2、3、6、6、3] mood =[1、1、0、0、0] k =2の場合、mood [2を設定すると、出力は17になります。 ]とmood[3]を1にすると、合計の気分は2 + 3 + 6 + 6=17人の顧客に満足します。

これを解決するには、次の手順に従います-

• n：=気分の大きさ
• a：=サイズ（n + 1）のリストで、0で埋めます
• s：=0
• 0からn-1の範囲のiの場合、do
  • a [i + 1]：=a [i]
  • mood [i]がゼロ以外の場合、
    • s：=s+顧客[i]
  • それ以外の場合、
    • a [i + 1]：=a [i +1]+顧客[i]
• d：=0
• kからnの範囲のiについては、
  • d：=最大dおよび（a [i] --a [i --k]）
• return 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