在 Python 中查找购买所有 N 个糖果的最小和最大金额

假设有一家糖果店，出售 N 种不同类型的糖果，并且所有 N 种不同类型糖果的价格都已给出。该商店还提供一项有吸引力的优惠。根据此优惠，我们可以从商店购买一件糖果，并最多免费获得 K 种其他不同类型的糖果。我们必须找到购买所有 N 种不同类型糖果所需的最低金额。我们还必须找到购买所有 N 种不同类型糖果所需的最大金额。在这两种情况下，我们都必须利用优惠并获得尽可能多的糖果。如果有 k 个或更多糖果可用，我们必须为每次购买糖果选择 k 个糖果。但是，如果可用糖果少于 k 个，则我们必须为每次购买糖果选择所有糖果。

因此，如果输入类似于 price = [4, 3, 2, 5] 且 k = 2，则输出将为 Minimum = 5 且 Maximum = 9。这是因为当 k 为 2 时，如果我们购买一个糖果，我们可以免费获得最多两个糖果。在第一种情况下，我们可以购买价格为 2 的糖果，并免费获得价格为 4 和 5 的糖果，我们也可以购买价格为 3 的糖果，因此最低成本 = 2 + 3 = 5。另一方面，在第二种情况下，我们购买价格为 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

  • 返回 res

  • 定义一个函数 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

  • 返回 res

  • 从主方法调用这两个函数以获取结果

  • 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

更新于: 2020-08-20

834 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告