비용이라는 목록이 있다고 가정합니다. 비용[i]에 [c1, c2]가 있는 경우 사람 i가 도시 0에 도달하는 데 비용 c1이 필요하고 도시 1에 도달하는 데 c2 비용이 든다는 것을 나타냅니다. 우리는 동일한 수의 사람들이 도시 1과 도시 0에 가기를 원합니다. 필요한 최소 비용을 찾아야 합니다.
따라서 입력이 비용 =[[2, 6],[10, 3],[4, 9],[5, 8]]과 같으면 출력은 17이 됩니다. 왜냐하면 사람 0과 2는 도시 0과 사람 1과 3이 도시 1로 이동하므로 도시 0의 경우 비용은 2+4 =6이고 도시 1의 경우 비용은 8+3 =11, 합계는 17입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- s :=0
- a :=새 목록
- 비용의 각 쌍(x, y)에 대해 다음을 수행합니다.
- s :=s + x
- 끝에 (y - x) 삽입
- 목록 정렬
- (크기 a / 2) - 1의 범위 0에서 i에 대해
- s :=s + a[i]
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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