在 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。
在线示例
让我们看看以下实现以获得更好的理解-
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