Pythonでリスト要素をイコライズするための最小総コストを見つけるプログラム

numsとcostsという2つの数値リストがあるとします。ここで、コストコスト[i]のnums[i]を増減できる操作があると考えてください。これらの操作はいくつでも実行でき、すべての要素をnumsで等しくしたいと考えています。必要な最小の総コストを見つける必要があります。

したがって、入力がnums =[3、2、4] cost =[1、10、2]のようである場合、1のコストで数値3を2に減らすことができるかのように、出力は5になります。それぞれ2のコストで、4を2回デクリメントできます。

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

• 関数helper（）を定義します。これはターゲットになります

• 合計：=0

• enumerate（nums）の各i、nについて、実行します

  • ターゲットがnと同じでない場合、

    • 合計：=合計+|n-ターゲット| *費用[i]

• 合計を返す

• mainメソッドから、次の手順を実行します。

• 低：=0、高：=最大数

• 低<高はゼロ以外ですが、実行

  • 中：=（低+高）/ 2

  • helper（mid）

    • 高：=中

  • それ以外の場合

    • 低：=中+ 1

• リターンヘルパー（低）

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

例

class Solution:
   def solve(self, nums, costs):
      def helper(target):
         total = 0
         for i,n in enumerate(nums):
            if target != n:
               total += abs(n-target) * costs[i]
         return total
      low,high = 0, max(nums)
      while low < high:
         mid = low + high >> 1
         if helper(mid) < helper (mid+1):
            high = mid
         else:
            low = mid + 1
      return helper(low)
ob = Solution()
nums = [3, 2, 4]
costs = [1, 10, 2]
print(ob.solve(nums, costs))

入力

[3, 2, 4], [1, 10, 2]

出力

5