สมมติว่าเรามีรายการตัวเลขที่เรียกว่าบันทึกและขีดจำกัดค่าอื่น แต่ละองค์ประกอบในบันทึก[i] แสดงถึงขนาดของบันทึกที่สร้างโดยผู้ใช้คนที่ i และขีดจำกัดแสดงถึงขนาดรวมของบันทึกที่เราสามารถจัดเก็บไว้ในฐานข้อมูลของเรา เราต้องหา x ที่ใหญ่ที่สุด ซึ่งถ้าเราตัดทอนทุกบันทึกในบันทึกให้เหลือขนาดสูงสุด x และผลรวมของขนาดบันทึกด้านซ้ายจะมีขนาดสูงสุด หากไม่จำเป็นต้องตัดบันทึก ให้คืนค่าขนาดบันทึกที่ใหญ่ที่สุด
ดังนั้น หากอินพุตเหมือนกับ logs =[500, 200, 10000, 500, 4000] limit =3000 เอาต์พุตจะเป็น 900 เพราะเราตัดทอนบันทึกเป็น 900 เราก็จะได้ [500, 200, 900, 500 , 900] ตอนนี้ผลรวมคือ 3000
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- หล่อ :=0
- สวัสดี :=1 + บันทึกสูงสุด
- ในขณะที่หล่อ + 1 <สวัสดี ทำ
- mi :=lo + ชั้นของ (hi - lo)/2
- ถ้าผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ในรายการด้วย (ขั้นต่ำของ mi และบันทึกสำหรับบันทึกการเข้าสู่ระบบแต่ละครั้ง) <=ขีด จำกัด แล้ว
- หล่อ :=ไมล์
- มิฉะนั้น
- สวัสดี :=ไมล์
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(logs, limit): lo, hi = 0, max(logs) + 1 while lo + 1 < hi: mi = lo + (hi - lo) // 2 if sum(min(mi, log) for log in logs) <= limit: lo = mi else: hi = mi return lo logs = [500, 200, 10000, 500, 4000] limit = 3000 print(solve(logs, limit))
อินพุต
[500, 200, 10000, 500, 4000], 3000
ผลลัพธ์
900
