Chương trình tìm giới hạn tối thiểu của quả bóng trong túi bằng Python

Giả sử chúng ta có một nums mảng trong đó phần tử thứ i chỉ ra một túi chứa nums [i] số quả bóng. Chúng tôi cũng có một giá trị khác được gọi là mx. Chúng tôi có thể thực hiện thao tác sau nhiều nhất là mx lần -

• Chọn một túi bóng bất kỳ và chia thành hai túi mới với ít nhất một quả bóng.

• Ở đây hình phạt là số lượng bóng tối đa trong một túi.

Chúng tôi phải giảm thiểu hình phạt sau khi hoạt động. Vì vậy, cuối cùng, chúng tôi phải tìm ra hình phạt tối thiểu có thể có sau khi thực hiện các hoạt động.

Vì vậy, nếu đầu vào là nums =[4,8,16,4], mx =4, thì đầu ra sẽ là 4 vì chúng ta có thể thực hiện các phép toán sau:Ban đầu chúng ta có các túi như [4,8,16,4] , chia túi có 16 quả bóng như [4,8,8,8,4], sau đó cho mỗi túi có 8 quả bóng, chia chúng thành hai túi với mỗi túi 4 quả bóng, như vậy mảng sẽ giống như [4,4,4, 8,8,4], sau đó là [4,4,4,4,4,8,4] và cuối cùng là [4,4,4,4,4,4,4,4], vì vậy ở đây tối thiểu chúng ta có 4 quả bóng , đó là hình phạt.

Để 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 trợ giúp (). Điều này sẽ lấy mục tiêu, mx

• nếu mục tiêu giống 0 thì

  • trả về mx + 1

• đếm:=0

• đối với mỗi số trong số, thực hiện

  • count:=count + thương số của (num - 1) / target

• số lượng trả về <=mx

• Từ phương thức chính, hãy thực hiện như sau

• left:=tối đa của thương số của (tổng tất cả các phần tử của nums / (kích thước của nums + mx)) và 1

• right:=tối đa là nums

• trong khi trái

  • mid:=quotient of (left + right) / 2

  • nếu helper (mid, mx) khác 0 thì

    • right:=mid

  • nếu không,

    • left:=mid + 1

• quay lại bên trái

Ví dụ

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

def helper(target, mx):
   if target == 0:
      return mx + 1
   count = 0
   for num in nums:
      count += (num - 1) // target
   return count <= mx

def solve(nums, mx):
   left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
   while left < right:
      mid = (left + right) // 2
      if helper(mid, mx):
         right = mid
      else:
         left = mid + 1
   return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

Đầu vào

[4,8,16,4], 4

Đầu ra

4