Tìm số tiền tối thiểu và tối đa để mua tất cả N kẹo bằng Python

Giả sử có một cửa hàng bán kẹo với N loại kẹo khác nhau và giá của tất cả N loại kẹo khác nhau được đưa ra. Cửa hàng cũng cung cấp một đề nghị hấp dẫn. Theo ưu đãi này, chúng ta có thể mua một viên kẹo duy nhất từ ​​cửa hàng và nhận được tối đa K loại kẹo khác nhau miễn phí. Ta phải tìm số tiền tối thiểu phải bỏ ra để mua tất cả N loại kẹo khác nhau. Chúng ta cũng phải tìm số tiền tối đa mà chúng ta phải bỏ ra để mua tất cả N loại kẹo khác nhau. Từ cả hai trường hợp, chúng tôi phải sử dụng phiếu mua hàng và lấy lại số kẹo tối đa có thể. Nếu có k hoặc nhiều kẹo hơn, chúng ta phải chọn k kẹo cho mỗi lần mua kẹo. Tuy nhiên, nếu có ít hơn k kẹo, chúng ta phải chọn tất cả kẹo để mua kẹo.

Vì vậy, nếu đầu vào là giá =[4, 3, 2, 5] và k =2, thì đầu ra sẽ là Tối thiểu =5 và Tối đa =9. Điều này là do khi k bằng 2, nếu chúng ta mua một viên kẹo và chúng tôi có thể lấy tối đa hai cái nữa miễn phí. Trong trường hợp đầu tiên, chúng ta có thể mua kẹo có giá 2 và lấy kẹo có giá trị 4 và 5 miễn phí, chúng ta cũng có thể mua kẹo có giá trị 3, do đó chi phí tối thiểu =2 + 3 =5. Mặt khác, trong thứ hai trường hợp chúng ta mua kẹo có giá 5 và lấy kẹo có giá 2 và 3 miễn phí, hoặc chúng ta cũng có thể mua kẹo có giá 4. do đó, chi phí tối đa =4 + 5 =9.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm get_min (). Điều này sẽ mất A, k

• n:=kích thước của A

• sắp xếp danh sách A

• res:=0, i:=0

• trong khi n khác 0, thực hiện

  • res:=res + A [i]

  • n:=n-k

  • i:=i + 1

• trả lại res

• Định nghĩa một hàm get_max (). Điều này sẽ mất A, k

• n:=kích thước của A

• sắp xếp danh sách A

• res:=0, idx:=0

• i:=n-1

• while i> =idx, do

  • res:=res + A [i]

  • idx:=idx + k

  • i:=i - 1

• trả lại res

• Từ phương thức chính, hãy gọi hai hàm này để nhận kết quả

• get_min (A, k)

• get_max (A, k)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[4, 3, 2, 5], 2

Đầu ra

5 9