|
| 1 | +/** |
| 2 | + * 2463. Minimum Total Distance Traveled |
| 3 | + * https://leetcode.com/problems/minimum-total-distance-traveled/ |
| 4 | + * Difficulty: Hard |
| 5 | + * |
| 6 | + * There are some robots and factories on the X-axis. You are given an integer array robot where |
| 7 | + * robot[i] is the position of the ith robot. You are also given a 2D integer array factory where |
| 8 | + * factory[j] = [positionj, limitj] indicates that positionj is the position of the jth factory |
| 9 | + * and that the jth factory can repair at most limitj robots. |
| 10 | + * |
| 11 | + * The positions of each robot are unique. The positions of each factory are also unique. Note |
| 12 | + * that a robot can be in the same position as a factory initially. |
| 13 | + * |
| 14 | + * All the robots are initially broken; they keep moving in one direction. The direction could be |
| 15 | + * the negative or the positive direction of the X-axis. When a robot reaches a factory that did |
| 16 | + * not reach its limit, the factory repairs the robot, and it stops moving. |
| 17 | + * |
| 18 | + * At any moment, you can set the initial direction of moving for some robot. Your target is to |
| 19 | + * minimize the total distance traveled by all the robots. |
| 20 | + * |
| 21 | + * Return the minimum total distance traveled by all the robots. The test cases are generated |
| 22 | + * such that all the robots can be repaired. |
| 23 | + * |
| 24 | + * Note that: |
| 25 | + * - All robots move at the same speed. |
| 26 | + * - If two robots move in the same direction, they will never collide. |
| 27 | + * - If two robots move in opposite directions and they meet at some point, they do not collide. |
| 28 | + * They cross each other. |
| 29 | + * - If a robot passes by a factory that reached its limits, it crosses it as if it does not exist. |
| 30 | + * - If the robot moved from a position x to a position y, the distance it moved is |y - x|. |
| 31 | + */ |
| 32 | + |
| 33 | +/** |
| 34 | + *@param {number[]} robot |
| 35 | + *@param {number[][]} factory |
| 36 | + *@return {number} |
| 37 | + */ |
| 38 | +varminimumTotalDistance=function(robot,factory){ |
| 39 | +robot.sort((a,b)=>a-b); |
| 40 | +factory.sort((a,b)=>a[0]-b[0]); |
| 41 | + |
| 42 | +constrobotCount=robot.length; |
| 43 | +constfactoryCount=factory.length; |
| 44 | +constmemo=newArray(robotCount+1).fill(null).map(()=>newArray(factoryCount+1).fill(-1)); |
| 45 | + |
| 46 | +returncalculateMinDistance(0,0); |
| 47 | + |
| 48 | +functioncalculateMinDistance(robotIndex,factoryIndex){ |
| 49 | +if(robotIndex===robotCount)return0; |
| 50 | +if(factoryIndex===factoryCount)return1e18; |
| 51 | + |
| 52 | +if(memo[robotIndex][factoryIndex]!==-1){ |
| 53 | +returnmemo[robotIndex][factoryIndex]; |
| 54 | +} |
| 55 | + |
| 56 | +letresult=calculateMinDistance(robotIndex,factoryIndex+1); |
| 57 | + |
| 58 | +lettotalDistance=0; |
| 59 | +for(letrobotsTaken=0;robotsTaken<factory[factoryIndex][1] |
| 60 | +&&robotIndex+robotsTaken<robotCount;robotsTaken++){ |
| 61 | +totalDistance+=Math.abs(robot[robotIndex+robotsTaken]-factory[factoryIndex][0]); |
| 62 | +result=Math.min( |
| 63 | +result, |
| 64 | +totalDistance+calculateMinDistance(robotIndex+robotsTaken+1,factoryIndex+1) |
| 65 | +); |
| 66 | +} |
| 67 | + |
| 68 | +memo[robotIndex][factoryIndex]=result; |
| 69 | +returnresult; |
| 70 | +} |
| 71 | +}; |