Chương trình tìm độ dài tối đa của k ruy-băng có cùng độ dài bằng Python

Giả sử chúng ta có một danh sách các số dương, đại diện cho độ dài của dải băng và cũng có một giá trị k. Chúng ta có thể cắt các đoạn ruy băng bao nhiêu lần tùy thích, chúng ta phải tìm độ dài r lớn nhất sao cho có k đoạn ruy băng có độ dài r. Nếu chúng tôi không thể tìm thấy giải pháp như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào là ruy-băng =[1, 2, 5, 7, 15] k =5, thì đầu ra sẽ là 5, vì chúng ta có thể cắt dải băng có kích thước 15 thành 3 đoạn dài mỗi đoạn là 5. Sau đó, cắt dải ruy băng có kích thước 7 thành kích thước 2 và 5. Và có một dải ruy băng khác có kích thước 5, vậy chúng ta có tổng cộng 5 dải ruy băng cho kích thước 5.

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

• trái:=0
• right:=tối đa các dải ruy băng
• khi left
• giữa:=tầng của (trái + phải + 1) / 2
• nếu tổng của tất cả các phần tử có trong danh sách chứa (tầng của ribbonLen / giữa cho mỗi ribbonLen trong các dải có ít nhất k), thì
  • left:=mid
• nếu không,
  • right:=mid - 1

Ví dụ

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

def solve(ribbons, k):
   left = 0
   right = max(ribbons)
   while left < right:
      mid = (left + right + 1) // 2
      if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
         left = mid
      else:
         right = mid - 1
   if left:
      return left
   return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

Đầu vào

[1, 2, 5, 7, 15], 5

Đầu ra

5