1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
# 2463. Minimum Total Distance Traveled
"""
there are some robots and factories on the x-axis. you are given an integer
array 'robot' where 'robot[i]' is the position of the i'th robot. you are
also given a 2d integer array 'factory' where 'factory[j] = [position_i,
limit_i]' indicates that 'position[j]' is the position of the j'th factory
and that the j'th factory can repair at most 'limit[j]' robots. the positions
of each robot are unique. note that a robot can be in the same position as a
factory initially. all the robots are initially broke; they keep moving in
one direction. the direction could be the negative or positive direction of
the x-axis. when a robot reaches a factory that did not reach its limit, the
factory repairs the robot and it stops moving. return the minimum total
distance traveled by all the robots. the test cases are generated as such
that all the robots can be repaired.
"""
class Solution(object):
def minimumTotalDistance(self, robot, factory):
"""
:type robot: List[int]
:type factory: List[List[int]]
:rtype: int
"""
n, m = len(robot), len(factory)
dp = [float("inf")] * (n + 1)
dp[n] = 0
robot.sort()
factory.sort()
for j in range(m - 1, -1, -1):
for i in range(n):
curr = 0
for k in range(1, min(factory[j][1], n - i) + 1):
curr += abs(robot[i + k - 1] - factory[j][0])
dp[i] = min(dp[i], dp[i + k] + curr)
return dp[0]
if __name__ == "__main__":
obj = Solution()
print(obj.minimumTotalDistance(robot=[0, 4, 6], factory=[[2, 2], [6, 2]]))
print(obj.minimumTotalDistance(robot=[1, -1], factory=[[-2, 1], [2, 1]]))
|