Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonの2つの異なる都市に同じ数の人々を送るための最小コストを見つけるためのプログラム

コストというリストがあるとします。 cost [i]に[c1、c2]がある場合、人iの場合、都市0に到達するのにc1の金額がかかり、都市1に到達するのにc2の金額がかかります。必要な最小コストを見つける必要があります。

したがって、入力がcosts =[[2、6]、[10、3]、[4、9]、[5、8]]のようである場合、人0と2は次のようになるため、出力は17になります。都市0と人1および3から都市1まで、したがって都市0の場合のコストは2 + 4 =6であり、都市1の場合のコストは8 + 3 =11であり、合計は17です。

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

  • s：=0
  • a：=新しいリスト
  • コストの各ペア（x、y）について、
    • s：=s + x
    • 最後に（y --x）をaに挿入します
  • リストを並べ替える
  • 範囲0から（a / 2のサイズ）-1のフロアのiの場合、do
    • s：=s + a [i]
  • return s

例

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

def solve(costs):
   s = 0
   a = []
   for x, y in costs:
      s += x
      a += (y - x,)
   a.sort()
   for i in range(len(a) // 2):
      s += a[i]
   return s

costs = [[2, 6],[10, 3],[4, 9],[5, 8]]
print(solve(costs))

入力

[[2, 6],[10, 3],[4, 9],[5, 8]]

出力

17

  1. Pythonでスティックをカットするための最小コストを見つけるためのプログラム

    値nとcutsという配列があるとします。長さn単位の木の棒があると考えてください。スティックには0からnまでのラベルが付いています。ここで、cuts [i]は、カットできる位置を表します。順番にカットする必要がありますが、カットの順番は自由に変更できます。ここで、1カットのコストはカットするスティックのサイズであり、合計コストはすべてのカットのコストの合計です。削減の最小総コストを見つける必要があります。 したがって、入力がn =7、cuts =[5,1,4,3]の場合、出力は16になります。これは、[3,5,1,4]のように注文すると、最初に長さ7から3なので、コストは7です。次に、長さ3

  2. Pythonですべてのポイントを接続するための最小コストを見つけるためのプログラム

    （x、y）の形式のいくつかの点を持つpointsという配列があるとします。ここで、2つのポイント（xi、yi）と（xj、yj）を接続するコストは、それらの間のマンハッタン距離であり、式は| xi--xj|です。 + | yi--yj|。すべてのポイントを接続するための最小コストを見つける必要があります。 したがって、ここでの合計距離は（6 + 5 + 3 + 8）=22です。 これを解決するには、次の手順に従います- points_set：=範囲0からポイントのサイズ-1までの数値を保持する新しいセット ヒープ：=ペア（0、0）でヒープを作成します visited_node：