Giả sử chúng ta có một danh sách được gọi là chi phí. Trong đó chi phí [i] có [c1, c2] cho biết rằng đối với người tôi, chi phí c1 để đến thành phố 0 và chi phí c2 để đến thành phố 1. Chúng tôi muốn cùng một số người đến thành phố 0 như thành phố 1, chúng tôi phải tìm chi phí tối thiểu cần thiết.
Vì vậy, nếu đầu vào giống như chi phí =[[2, 6], [10, 3], [4, 9], [5, 8]], thì đầu ra sẽ là 17, vì người 0 và 2 sẽ chuyển đến thành phố 0 và người 1 và 3 đến thành phố 1, vì vậy đối với thành phố 0, chi phí là 2 + 4 =6, và đối với thành phố 1, chi phí là 8 + 3 =11, tổng là 17.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- s:=0
- a:=một danh sách mới
- đối với mỗi cặp (x, y) trong chi phí, hãy thực hiện
- s:=s + x
- chèn (y - x) vào cuối
- sắp xếp danh sách một
- đối với tôi trong phạm vi từ 0 đến tầng của (cỡ a / 2) - 1, thực hiện
- s:=s + a [i]
- trả lại s
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[[2, 6],[10, 3],[4, 9],[5, 8]]
Đầu ra
17