최소 총 이동 거리

2463. 최소 총 이동 거리

난이도:어려움

주제: 배열, 동적 프로그래밍, 정렬

X축에는 로봇과 공장이 있습니다. 로봇[i]가 i^번째 로봇의 위치인 정수 배열 로봇이 주어졌습니다. 또한 2D 정수 배열 팩토리가 제공됩니다. 여기서 Factory[j] = [position_j,limit_j]는 position_j이 j의 위치임을 나타냅니다. _번째 공장이고 j_번째 공장은 최대 수리 가능 제한_j로봇.

각 로봇의 위치는 고유합니다. 각 공장의 위치도 특이합니다. 로봇은 초기에 공장과 같은 위치에 있을 수 있습니다.

모든 로봇은 처음에는 고장났습니다. 그들은 한 방향으로 계속 움직입니다. 방향은 X축의 음수 방향 또는 양수 방향일 수 있습니다. 로봇이 한계에 도달하지 못한 공장에 도달하면 공장에서는 로봇을 수리하고 로봇은 움직이지 않게 됩니다.

언제든지일부 로봇의 초기 이동 방향을 설정할 수 있습니다. 당신의 목표는 모든 로봇이 이동하는 총 거리를 최소화하는 것입니다.

모든 로봇이 이동한 최소 총 거리를 반환합니다. 모든 로봇을 수리할 수 있도록 테스트 케이스가 생성됩니다.

참고

• 모든 로봇은 같은 속도로 움직입니다.
• 두 로봇이 같은 방향으로 움직이면 절대 충돌하지 않습니다.
• 두 로봇이 반대 방향으로 움직이다가 어느 시점에서 만나면 충돌하지 않습니다. 서로 교차합니다.
• 로봇이 한계에 도달한 공장 앞을 지나가면 마치 존재하지 않는 것처럼 지나갑니다.
• 로봇이 x 위치에서 y 위치로 이동했다면 이동한 거리는 |y - x|입니다.

예 1:

• 입력: 로봇 = [0,4,6], 공장 = [[2,2],[6,2]]
• 출력: 4
• 설명: 그림과 같이:
  • 위치 0의 첫 번째 로봇이 양의 방향으로 이동합니다. 1차 공장에서 수리해드립니다.
  • 위치 4의 두 번째 로봇이 음의 방향으로 이동합니다. 1차 공장에서 수리해드립니다.
  • 6번 위치의 세 번째 로봇은 두 번째 공장에서 수리할 예정입니다. 움직일 필요는 없습니다.
  • 첫 번째 공장의 제한은 2개이며, 로봇 2개를 고정했습니다.
  • 제2공장의 제한은 2개이며, 로봇 1개를 고쳤습니다.
  • 총 거리는 |2 - 0| |2 - 4| |6 - 6| = 4. 4보다 더 나은 총 거리를 달성할 수 없음을 알 수 있습니다.

예 2:

• 입력: 로봇 = [1,-1], 공장 = [[-2,1],[2,1]]
• 출력: 2
• 설명: 그림과 같이:
  • 위치 1의 첫 번째 로봇이 양의 방향으로 이동합니다. 제2공장에서 수리할 예정입니다.
  • -1 위치에 있는 두 번째 로봇이 음의 방향으로 이동합니다. 1차 공장에서 수리해드립니다.
  • 첫 번째 공장의 제한은 1개이며, 로봇 1개를 고정했습니다.
  • 제2공장의 제한은 1개이며, 로봇 1개를 고쳤습니다.
  • 총 거리는 |2 - 1| |(-2) - (-1)| = 2. 2보다 더 나은 총 거리를 달성할 수 없음을 알 수 있습니다.

제약조건:

• 1 <= 로봇.길이, 공장.길이 <= 100
• factory[j].length == 2
• -10⁹ <= 로봇[i], 위치j <= 10⁹
• 0 <= 제한_j <= 로봇 길이
• 모든 로봇을 항상 수리할 수 있도록 입력이 생성됩니다.

힌트:

1. 로봇과 공장을 위치별로 정렬하세요.
2. 분류 후에는 각 공장에서 로봇의 일부 하위 부분을 수리해야 합니다.
3. 퍼스트J공장에서 퍼스트i로봇을 수리하기 위한 최소 총거리를 찾아보세요.

해결책:

정렬된 로봇과 공장 배열을 통해 동적 프로그래밍을 사용할 수 있습니다. 각 공장의 수리 능력을 존중하면서 각 로봇이 공장에서 수리를 받기 위해 이동해야 하는 거리를 최소화하는 것이 아이디어입니다. 다음은 접근 방식을 단계별로 분석한 것입니다.

1. 로봇과 공장 배열을 위치별로 정렬하세요. 정렬을 하면 근처에 있는 로봇을 근처 공장에 배정할 수 있어 이동 거리를 최소화하는 데 도움이 됩니다.

2. 동적 프로그래밍 접근 방식: 2D DP 테이블 dp[i][j]를 정의합니다. 여기서:

   • i는 최초의 i로봇을 대표합니다.
   • j는 최초의 j공장을 의미합니다.
   • dp[i][j]는 j개의 공장을 사용하여 i개의 로봇을 수리하기 위한 최소 총 거리를 저장합니다.

3. 상태 전환:

   • 각 공장마다 한도 내에서 연속 로봇의 하위 집합을 수리해 보세요.
   • 위치 p에 있는 공장 j의 경우 각 로봇에서 공장 위치까지의 거리를 합산하여 k개의 로봇을 할당하는 데 필요한 최소 거리를 계산합니다.
   • 더 적은 수의 로봇을 수리하거나 공장 용량을 최대한 활용하는 것 중에서 최소값을 선택하여 DP 상태를 업데이트하세요.

이 솔루션을 PHP로 구현해 보겠습니다: 2463. 최소 총 이동 거리

  
  
  설명:




정렬: 로봇과 공장을 위치별로 정렬하여 인근 로봇을 인근 공장에 배정합니다.

DP 초기화: 공장에서 수리된 로봇이 없으면 거리가 0임을 의미하므로 dp[0][0] = 0으로 초기화합니다.

동적 프로그래밍 전환:


각 공장 j에 대해 그 앞에 있는 k개의 로봇을 한도 내에서 수리해 봅니다.
총 거리는 sumDist에 누적됩니다.
k개의 로봇을 수리한 후 거리와 이전 상태를 고려하여 dp[i][j]를 최소값으로 업데이트합니다.








  
  
  복잡성




시간 복잡도: O(n * m * L) 여기서 n은 로봇 수, m은 공장 수, L은 공장에서 처리할 수 있는 최대 수리 한도입니다.

공간 복잡도: DP 테이블의 경우 O(n * m)


이 솔루션은 공장 한도 내에서 수리할 모든 로봇의 최소 이동 거리를 효율적으로 계산합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 최소 총 이동 거리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!