สมมติว่าเรามีรายการของตัวเลขที่เรียกว่ากองและค่า k กอง[i] หมายถึง จำนวนของก้อนหินบนกอง i. ในแต่ละชั่วโมง เราเลือกกองและนำหินจำนวน r ออกจากกองนั้น ถ้าเราเลือกกองที่มีหินน้อยกว่า r ก็ยังต้องใช้เวลาหนึ่งชั่วโมงในการกำจัดกอง เราต้องหาค่าต่ำสุดของ r เพื่อให้เราสามารถเอาหินทั้งหมดออกในเวลาน้อยกว่าหรือเท่ากับ k ชั่วโมง
ดังนั้น ถ้าอินพุตเป็นเหมือนกอง =[3, 6, 4] k =5 แล้วผลลัพธ์จะเป็น 3 เพราะสำหรับ r =3 ก้อนหินต่อชั่วโมง เราสามารถล้างกองที่สองใน 2 ชั่วโมง แล้วล้าง ที่สามใน 2 ชั่วโมง และเคลียร์กองแรกใน 1 ชั่วโมง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- l :=1
- h :=จำนวนสูงสุด
- r :=h
- กำหนดฟังก์ชัน turns() นี่จะใช้เวลา r
- ส่งคืนผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ในรายการด้วย (เพดานของ b / r สำหรับแต่ละ b ในกอง)
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ในขณะที่ l
- กลาง :=ชั้นของ (l + h) / 2
- ถ้าเลี้ยว(กลาง)> k แล้ว
- l :=กลาง + 1
- มิฉะนั้น
- h :=กลาง
- r :=ขั้นต่ำของ r และ mid
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from math import ceil def solve(piles, k): l = 1 h = max(piles) r = h def turns(r): return sum(ceil(b / r) for b in piles) while l < h: mid = (l + h) // 2 if turns(mid) > k: l = mid + 1 else: h = mid r = min(r, mid) return r piles = [3, 6, 4] k = 5 print(solve(piles, k))
อินพุต
[3, 6, 4], 5
ผลลัพธ์
3
