โปรแกรมหาขีด จำกัด ขั้นต่ำของลูกบอลในกระเป๋าใน Python

สมมติว่าเรามีจำนวนอาร์เรย์ที่องค์ประกอบ ith ระบุถุงที่มีจำนวนลูกบอล nums[i] เรายังมีค่าอื่นที่เรียกว่า mx เราสามารถดำเนินการต่อไปนี้ได้สูงสุด mx ครั้ง -

• เลือกถุงลูกใดก็ได้แล้วแบ่งเป็นถุงใหม่สองใบโดยมีลูกบอลอย่างน้อยหนึ่งลูก

• บทลงโทษในที่นี้คือจำนวนบอลสูงสุดในกระเป๋า

เราต้องลดโทษให้น้อยที่สุดหลังการผ่าตัด ในที่สุด เราก็ต้องหาค่าปรับขั้นต่ำที่เป็นไปได้หลังจากดำเนินการ

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4,8,16,4], mx =4 ผลลัพธ์จะเป็น 4 เพราะเราสามารถดำเนินการต่อไปนี้ได้:เริ่มแรกเรามีถุงเช่น [4,8,16,4] แยกถุงมี 16 ลูก เช่น [4,8,8,8,4] จากนั้นให้แต่ละถุงมี 8 ลูก แบ่งเป็น 2 ถุงๆละ 4 ลูก ดังนั้นอาร์เรย์จะเป็นแบบ [4,4,4, 8,8,4] จากนั้น [4,4,4,4,4,8,4] และสุดท้าย [4,4,4,4,4,4,4,4,4] ดังนั้นที่นี่ขั้นต่ำเรามี 4 ลูก , นั่นคือบทลงโทษ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชั่น helper() นี่จะเป็นเป้าหมาย mx

• ถ้าเป้าหมายเท่ากับ 0 แล้ว

  • คืนค่า mx + 1

• นับ :=0

• สำหรับแต่ละ num เป็น num ทำ

  • count :=count + ผลหารของ (num - 1)/target

• จำนวนคืน <=mx

• จากวิธีหลัก ให้ทำดังนี้

• ซ้าย :=สูงสุดของผลหารของ (ผลรวมขององค์ประกอบทั้งหมดของ nums /(ขนาดของ nums + mx)) และ 1

• right :=จำนวนสูงสุด

• ขณะที่ซ้าย <ขวา ทำ

  • mid :=ผลหารของ (ซ้าย + ขวา)/2

  • ถ้า helper(mid, mx) ไม่ใช่ศูนย์ แล้ว

    • ขวา :=กลาง

  • มิฉะนั้น

    • ซ้าย :=กลาง + 1

• กลับซ้าย

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

[4,8,16,4], 4

ผลลัพธ์

4