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

คำอธิบายปัญหา

กำหนดลิสต์ความยาวสายริบบิ้น ribbons และ k ตัดสายได้อย่างอิสระ หา **ความยาว r สูงสุด** ที่ได้สาย k เส้นยาว r พอดี ไม่ได้คืน -1

ตัวอย่าง

ribbons = [1, 2, 5, 7, 15], k = 5 → Output: 5

• 15 → 3 เส้นยาว 5
• 7 → 1 เส้นยาว 5 (เหลือ 2)
• 5 → 1 เส้นยาว 5
• รวม 5 เส้น ✓

ขั้นตอนการแก้ปัญหา (Binary Search)

1. ช่วงคำตอบ: left=0, right=max(ribbons)
2. Mid = ความยาวลอง: นับจำนวนเส้น = sum(ribbon // mid for ribbon in ribbons)
3. ถ้า ≥ k → left = mid (ลองใหญ่ขึ้น) มิฉะนั้น right = mid - 1
4. คืน left หาก > 0 มิฉะนั้น -1

การตนการทำงาน (Python)

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

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

อินพุต / เอาต์พุต

Input:  [1, 2, 5, 7, 15], 5
Output: 5