동전 더미 수 (예 : 5 더미 : 9,0,5,1,5) 총 20 동전 ... 최소 번호. 모든 더미가 동전 (4,4,4,4,4)을 동등하게 가질 수 있도록 필요한 이동량 (9 개 이동) 규칙 : 하나의 동전을 인접한 더미에만 이동할 수 있습니다. j 번째 더미 동전은 j-1 또는 j + 1로 이동할 수 있습니다.인접한 동전 이동의 최소 수를 찾으시겠습니까?
퍼즐을 풀기위한 좋은 알고리즘은 무엇입니까?
모든 파일 크기의 산술 평균은 각 파일의 원하는 크기를 알려주며, 파일 개수는 n입니다. 처음에는 솔루션을 구성하는 동안보다 때때로 음수 크기의 더미를 가질 수 있다고 가정합니다. 잠시 후에 그 가정을 수정하겠습니다.
O (n) 알고리즘은 다음과 같습니다. 첫 번째 파일을 봅시다. 크기가 d 인 경우, 왼쪽에 더미가 없으므로 크기를 변경하거나 다른 더미에 동전을 전달하지 않으려합니다. 즉, 최적의 솔루션으로 이동하면이 더미의 크기가 변경되지 않으며,이를 잊어 버릴 수 있습니다. 그러나 첫 번째 더미의 크기가 d '> d라면, 우리는 동전을 (d'- d) 제거하려고합니다. 그들이 한 방향으로 만 갈 수 있기 때문에 - 오른쪽으로, 우리는 그것을 할 수 있습니다. 첫 번째 더미를 d로 줄이고, 전에했던 것처럼 그것을 잊어 버려야합니다. 비슷하게 d '< d이면 몇 번째 시점에서 두 번째 더미에서 동전을 가져와야하므로 첫 번째 더미를 잊어 버릴 것입니다.
우리는 우리가 삭제했다고 상상할 수있는 첫 번째 파일을 잊어 버렸고 두 번째 파일은 이제 첫 번째 파일입니다. 우리는 모든 더미를 통해이 과정을 진행합니다. 일부 동전을 움직이면 그 움직임을 카운터에 추가합니다.
왼쪽 음수 더미에는 한 가지 문제가 있습니다. 우리 솔루션에서 수행 한 모든 작업을 나열 해보면 실행 순서가 중요하지 않음을 쉽게 알 수 있습니다. 우리가 불법적으로 할 수 있었던 유일한 행동은 동전을 쌓아서 (i + 1) 동전을 쌓아서 (i + 1) 부정을 남겼을 때였습니다. 다시 말하면, 우리는 그것을 보상하기 위해 (i + 2)에서 (i + 1)까지 동전을 가져 갔고,이 이동이 (i + 1)에서 (i + 1)의 크기로 이동하기 전에 완료 되었다면 부정적이지 않을거야. 따라서 우리가 가장 오른쪽에서부터 시작하여 예정된 동작을 실행하면 모든 것이 잘 될 것입니다. 이것은 구축 된 솔루션이 유효 함을 증명합니다.