用 Python 找出购买所有 N 颗糖果的最小和最大金额

pythonserver side programmingprogramming更新于 2025/9/30 13:32:17

假设有一家糖果店,店里有 N 种不同类型的糖果,并且给出了所有 N 种不同类型的糖果的价格。商店还提供诱人的优惠。根据此优惠,我们可以从商店购买一颗糖果,并免费获得最多 K 种不同类型的其他糖果。我们必须找出购买所有 N 种不同类型的糖果所需花费的最低金额。我们还必须找出购买所有 N 种不同类型的糖果所需花费的最高金额。在这两种情况下,我们都必须利用优惠并获得尽可能多的糖果。如果有 k 种或更多糖果可供选择,我们必须为每次购买糖果选择 k 种糖果。但是,如果可用的糖果少于 k 个,我们必须选择所有糖果进行购买。

因此,如果输入为 price = [4, 3, 2, 5] 和 k = 2,则输出将为最小值 = 5 和最大值 = 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

  • while i>=idx, do

    • 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

相关文章


有用资源