Pythonで通りのすべての家を照らすための最小半径を見つけるプログラム

1次元の線上の家の位置を表すnumsと呼ばれる番号のリストがあるとします。ここで、ライン上のどこにでも配置できる3つの街路灯があり、位置xのライトが範囲[x --r、x+r]のすべての家を照らしているとします。すべての家を照らすのに必要な最小のrを見つける必要があります。

したがって、入力がnums =[4,5,6,7]のような場合、ランプを4.5、5.5、および6.5に配置して、r =0.5にすることができるため、出力は0.5になります。したがって、これらの3つのライトで4つの家すべてを照らすことができます。

これを解決するには、次の手順に従います-

• 関数valid（）を定義します。これにはrがかかります

• last_location：=nums [0] + r

• カウント：=1

• 0からnumsのサイズの範囲のiの場合、実行します

  • val：=nums [i]

  • val --last_location> rの場合、

    • count：=count + 1

    • last_location：=val + r

• カウント<=3の場合はtrueを返し、それ以外の場合はfalse

• メインの方法から、次のようにします-

• リスト番号を並べ替える

• 左：=0

• 右：=numsの最後の要素

• res：=inf

• itr：=0

• 左<=右、itr <20、実行

  • 中央：=左+（右-左）/ 2

  • valid（mid）がtrueの場合、

    • res：=resとmidの最小値

    • 右：=半ば

  • それ以外の場合

    • 左：=中央

    • itr：=itr + 1

• 解像度を返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, nums):
      def valid(r):
         last_location = nums[0] + r
         count = 1
         for i in range(len(nums)):
            val = nums[i]
            if val - last_location > r:
               count += 1
               last_location = val + r
         return count <= 3
      nums.sort()
      left = 0
      right = nums[-1]
      res = float("inf")
      itr = 0
      while left <= right and itr < 20:
         mid = left + (right - left) / 2
         if valid(mid):
            res = min(res, mid)
            right = mid
         else:
            left = mid
         itr += 1
      return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))

入力

[4,5,6,7]

出力

0.5