Tìm số tiền tối thiểu và tối đa để mua hết N loại kẹo trong Python

Cửa hàng kẹo có N loại với giá khác nhau. Mua 1 loại được tặng tối đa K loại khác miễn phí. Cần tìm số tiền tối thiểu và tối đa để mua hết N loại (phải tận dụng tối đa ưu đãi).

Ví dụ: price = [4,3,2,5], k=2 → Min=5 (mua 2 tặng 4,5; mua 3), Max=9 (mua 5 tặng 2,3; mua 4).

Giải thuật

• Tối thiểu: Sắp xếp giá tăng dần. Mua từ giá rẻ nhất, mỗi lần mua 1 loại được tặng K loại đắt nhất còn lại. Duyệt từ đầu mảng, mỗi bước bỏ qua K phần tử cuối.
• Tối đa: Sắp xếp giá tăng dần. Mua từ giá đắt nhất, mỗi lần mua 1 loại được tặng K loại rẻ nhất còn lại. Duyệt từ cuối mảng, mỗi bước bỏ qua K phần tử đầu.

Ví dụ

def get_min(A, k):
    n = len(A)
    A.sort()
    res = 0
    i = 0
    while n:
        res += A[i]
        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))

Đầu vào

[4, 3, 2, 5], 2

Đầu ra

5 9