โปรแกรมเพิ่มแรงขั้นต่ำระหว่างลูกบอลในถังให้สูงสุดใน Python

ปัญหา

มีตำแหน่งถัง pos และ x ลูกบอล แรงระหว่างลูกบอลที่ p,q คือ |p-q| วางลูกบอล x ลูกในตำแหน่งที่กำหนด ให้แรงขั้นต่ำระหว่างคู่อยู่ใดๆ สูงสุด

ตัวอย่าง

pos=[2,4,6,8,10,12], x=3 → ผลลัพธ์ 4 (วางที่ 4,8,12 แรงขั้นต่ำ = 4)

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน ball_count(d): นับลูกบอลที่วางได้ถ้าระยะห่างขั้นต่ำ d
   • ans:=1, curr:=pos[0]
   • วน i 1 ถึง n-1: ถ้า pos[i]-curr >= d: ans+=1; curr=pos[i]
   • คืน ans
2. n := len(pos), เรียง pos
3. Binary search: left=0, right=pos[-1]-pos[0]
   • mid = right - (right-left)//2
   • ถ้า ball_count(mid) >= x: left = mid มิฉะนั้น: right = mid-1
4. คืน left

การนำไปใช้งาน (Python)

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