สมมติว่าเราต้องออกแบบเครื่องทำความร้อนมาตรฐานที่มีรัศมีอบอุ่นคงที่เพื่อให้ความอบอุ่นกับบ้านทุกหลัง ตอนนี้ เราได้กำหนดตำแหน่งของบ้านและเครื่องทำความร้อนในแนวนอนแล้ว เราต้องหารัศมีขั้นต่ำของเครื่องทำความร้อนเพื่อให้เครื่องทำความร้อนเหล่านั้นครอบคลุมบ้านทุกหลัง ดังนั้น เราจะจัดหาบ้านและเครื่องทำความร้อนแยกกัน และผลลัพธ์ที่คาดหวังจะเป็นมาตรฐานรัศมีขั้นต่ำของเครื่องทำความร้อน
ดังนั้นหากอินพุตเป็น [1,2,3,4],[1,4] เอาต์พุตจะเป็น 1 เนื่องจากฮีตเตอร์สองตัวถูกวางในตำแหน่งที่ 1 และ 4 เราต้องใช้รัศมี 1 แล้วทั้งหมด บ้านก็อุ่นได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เรียงรายชื่อบ้าน
-
จัดเรียงรายการเครื่องทำความร้อน
-
res :=ขนาดอาร์เรย์เท่ากับ house array และเติมโดยใช้ inf
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาดของบ้าน ทำ
-
ชั่วโมง :=บ้าน[i]
-
ind :=ออกจากดัชนีส่วนใหญ่เพื่อแทรก h ลงในฮีตเตอร์เพื่อให้รายการยังคงถูกจัดเรียง
-
ถ้า ind เท่ากับขนาดฮีตเตอร์แล้ว
-
res[i] :=ขั้นต่ำของ res[i], |h - เครื่องทำความร้อน[-1]|
-
-
มิฉะนั้นเมื่อ ind เหมือนกับ 0 แล้ว
-
res[i] :=ขั้นต่ำของ res[i], |h - heaters[0]|
-
-
มิฉะนั้น
-
res[i] :=ขั้นต่ำของ res[i], |h - heaters[ind]| , |h - เครื่องทำความร้อน[ind-1]|
-
-
-
คืนค่าความละเอียดสูงสุด
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
จากการนำเข้า bisect bisect_leftclass วิธีแก้ไข:def findRadius(ตัวเอง บ้าน เครื่องทำความร้อน):houses.sort() heaters.sort() res =[float('inf')]*len(houses) สำหรับฉันในช่วง (len (บ้าน)):h =บ้าน[i] ind =bisect_left(เครื่องทำความร้อน, h) if ind==len(เครื่องทำความร้อน):res[i] =นาที(res[i], abs(h - เครื่องทำความร้อน[-1]) ) elif ind ==0:res[i] =min(res[i], abs(h - heaters[0])) else:res[i] =min(res[i], abs(h - heaters[ind]) ]), abs(h - heaters[ind-1])) return max(res)ob =Solution()print(ob.findRadius([1,2,3,4],[1,4])) อินพุต
[1,2,3,4],[1,4]
ผลลัพธ์
1
