PythonでN個すべてのキャンディーを購入するための最小額と最大額を見つける

N種類のキャンディーが販売されているキャンディーストアがあり、N種類すべてのキャンディーの価格が示されているとします。この店は魅力的なオファーも提供しています。このオファーによると、ストアからキャンディーを1つ購入して、最大K種類の他のキャンディーを無料で入手できます。 N種類すべてのキャンディーを購入するために費やす必要のある最小金額を見つける必要があります。また、N種類のキャンディーをすべて購入するために費やす必要のある最大金額を見つける必要があります。どちらの場合も、オファーを利用して、可能な限り最大のキャンディーを取り戻す必要があります。 k個以上のキャンディーがある場合は、キャンディーを購入するたびにk個のキャンディーを選択する必要があります。ただし、入手可能なキャンディーがk個未満の場合は、キャンディーを購入するためにすべてのキャンディーを選択する必要があります。

したがって、入力がprice =[4、3、2、5]およびk =2の場合、出力は最小=5および最大=9になります。これは、kが2の場合、キャンディーを1つ購入すると最大2つまで無料でご利用いただけます。最初のケースでは、2のキャンディーを購入し、4と5の価格のキャンディーを無料で購入できます。また、3のキャンディーも購入できるため、最小コスト=2 + 3 =5です。一方、2番目のケースでは5ドルのキャンディーを購入し、2と3の価格のキャンディーを無料で購入する場合、または4のキャンディーを購入することもできます。したがって、最大コスト=4 + 5 =9

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

• 関数get_min（）を定義します。これにはA、kがかかります

• n：=Aのサイズ

• リストを並べ替えるA

• res：=0、i：=0

• nがゼロ以外の場合、実行

  • res：=res + A [i]

  • n：=n-k

  • i：=i + 1

• 解像度を返す

• 関数get_max（）を定義します。これにはA、kが必要です

• n：=Aのサイズ

• リストを並べ替えるA

• res：=0、idx：=0

• i：=n-1

• i> =idxの場合、実行

  • res：=res + A [i]

  • idx：=idx + k

  • i：=i-1

• 解像度を返す

• メインメソッドからこれらの2つの関数を呼び出して、結果を取得します

• get_min（A、k）

• get_max（A、k）

例

理解を深めるために、次の実装を見てみましょう-

def get_min(A,k):
   n = len(A)
   A.sort()
   res = 0
   i=0
   while(n):
      res += A[i]
      n = n-k
      i += 1
   return res
def get_max(A, k):
   n = len(A)
   A.sort()
   res = 0
   idx = 0
   i=n-1
   while(i>=idx):
      res += A[i]
      idx += k
      i -= 1
   return res

A = [4, 3, 2, 5]
k = 2
print(get_min(A, k),get_max(A, k))

入力

[4, 3, 2, 5], 2

出力

5 9