[Leetcode] 2731. Movement of Robots (Medium)

概述

題目

https://leetcode.com/problems/movement-of-robots/
數線上有多個機器人，且給予之後前進方向左或右，經過 d 秒後，求所有機器人兩兩之間的相對距離總合

心得

數線模擬題 + 區段計算，一開始還亂猜以為會有不失一般性、吃一次 WA 後才發現要分開計算線段出現次數

Cross Road

思路

先確認 d 秒後機器人的位置都在哪邊，而後排序由小到大，再計算相鄰兩個機器人的距離，最終計算該距離會被使用到幾次

程式

class Solution(object):
    def sumDistance(self, nums, s, d):
        """
        :type nums: List[int]
        :type s: str
        :type d: int
        :rtype: int
        """
        n = len(s)
        MOD = 10**9+7

        # 最終位置並排序
        for i in range(n):
            if s[i] == "L":
                t = -1
            else:
                t = 1
            nums[i] += d*t
        nums.sort()

        # 計算間距
        arr = [nums[i+1]-nums[i] for i in range(n-1)]

        # 任兩點線段出現次數計算
        cnt = 0
        for i in range(n-1):
            cnt += ((1+i) * (n-1-i) * arr[i] )%MOD
        return cnt%MOD