สมมติว่าเราได้รับถังหลายถังและจำนวนลูกบอล x หากลูกบอลถูกใส่ลงไปในถัง แรงพิเศษจะกระทำอยู่ภายใน และเราต้องหาวิธีเพิ่มแรงขั้นต่ำระหว่างสองลูก แรงระหว่างสองลูกในตำแหน่ง p และ q คือ |p - q| ข้อมูลที่ป้อนให้กับเราคืออาร์เรย์ที่มีตำแหน่งถังและจำนวนลูก x เราต้องหาแรงขั้นต่ำระหว่างพวกมัน
ดังนั้น หากอินพุตเป็น pos =[2, 4, 6, 8, 10, 12], x =3 ผลลัพธ์จะเป็น 4
ลูกบอลสามารถวางในตำแหน่งที่กำหนดในอาร์เรย์ของถัง 12 ลูกบอลสามลูกสามารถวางในตำแหน่ง 4, 8 และ 12 และพลังระหว่างกันจะเป็น 4 ค่านี้ไม่สามารถเพิ่มได้อีก
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน ball_count() นี่จะใช้เวลา d
-
และ :=1
-
สกุลเงิน :=pos[0]
-
สำหรับผมอยู่ในช่วง 1 ถึง n ทำ
-
ถ้า pos[i] - curr>=d แล้ว
-
ans :=ans + 1
-
curr :=pos[i]
-
-
-
กลับมาอีกครั้ง
-
-
n :=ขนาดของ pos
-
เรียงลำดับรายการ pos
-
ซ้าย :=0
-
ขวา :=pos[-1] - pos[0]
-
ขณะที่ซ้าย <ขวา ทำ
-
mid :=right - floor value of((ขวา - ซ้าย) / 2)
-
ถ้า ball_count(กลาง)>=x แล้ว
-
ซ้าย :=กลาง
-
-
มิฉะนั้น
-
ขวา :=กลาง - 1
-
-
-
กลับซ้าย
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(pos, x): n = len(pos) pos.sort() def ball_count(d): ans, curr = 1, pos[0] for i in range(1, n): if pos[i] - curr >= d: ans += 1 curr = pos[i] return ans left, right = 0, pos[-1] - pos[0] while left < right: mid = right - (right - left) // 2 if ball_count(mid) >= x: left = mid else: right = mid - 1 return left print(solve([2, 4, 6, 8, 10, 12], 3))
อินพุต
[2, 4, 6, 8, 10, 12], 3
ผลลัพธ์
4
