โปรแกรมค้นหาความยาวสูงสุดของ k ribbon ที่มีความยาวเท่ากันใน Python

สมมุติว่าเรามีรายการจำนวนบวก แทนความยาวของริบบอนและมีค่า k หนึ่งค่า เราสามารถตัดริบบ้อนได้หลายครั้งตามต้องการ เราต้องหาริบบอนที่ยาวที่สุด r ให้ได้ k ริบบ้อนยาว r หากเราไม่พบวิธีแก้ปัญหาดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็นเหมือนริบบ้อน =[1, 2, 5, 7, 15] k =5 ผลลัพธ์จะเป็น 5 เนื่องจากเราสามารถตัดริบบ้อนขนาด 15 ออกเป็น 3 ชิ้น ยาว 5 ชิ้น จากนั้นตัดริบบิ้นขนาด 7 เป็นขนาด 2 และ 5 และมีริบบิ้นขนาด 5 อีกอัน ดังนั้นเราจึงได้ริบบิ้นขนาด 5 ทั้งหมด 5 เส้น

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

ซ้าย :=0
ขวา :=จำนวนริบบอนสูงสุด
ขณะซ้าย <ขวา ทำ
- กลาง :=ชั้นของ (ซ้าย + ขวา + 1) / 2
- ถ้าผลรวมขององค์ประกอบทั้งหมดที่อยู่ในรายการที่มี (พื้นของ ribbonLen / กลางสำหรับแต่ละ ribbonLen ใน ribbon ที่อย่างน้อย k) แล้ว
  - ซ้าย :=กลาง
- มิฉะนั้น
  - ขวา :=กลาง - 1
ถ้าเหลือไม่เป็นศูนย์
- กลับซ้าย
คืน -1

ตัวอย่าง

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

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

อินพุต

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