2731.移动机器人

链接：2731.移动机器人
难度：Medium
标签：脑筋急转弯、数组、前缀和、排序
简介：请你返回指令重复执行 d 秒后，所有机器人之间两两距离之和。

题解 1 - cpp

• 编辑时间：2023-10-10
• 执行用时：108ms
• 内存消耗：97.32MB
• 编程语言：cpp
• 解法介绍：贪心，忽略碰撞。

class Solution {
public:
    int sumDistance(vector<int>& nums, string s, int d) {
        long long n = nums.size(), res = 0, MOD = 1e9 + 7;
        vector<long long> arr;
        for (int i = 0; i < n; i++) {
            arr.push_back(s[i] == 'L' ? nums[i] - d : nums[i] + d);
        }
        sort(arr.begin(), arr.end());
        for (int i = 1; i < n; i++) {
            long long v = (arr[i] - arr[i - 1]) % MOD * (n - i) * i % MOD;
            res = (res + v) % MOD;
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-10-10
• 执行用时：136ms
• 内存消耗：26.55MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        n = len(nums)
        arr = [nums[i] - d if s[i] == 'L' else nums[i] + d for i in range(n)]
        arr.sort()
        return sum((arr[i] - arr[i - 1]) * (n - i) * i for i in range(1, n)) % 1000000007

题解 3 - rust

• 编辑时间：2023-10-10
• 执行用时：24ms
• 内存消耗：4.51MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn sum_distance(nums: Vec<i32>, s: String, d: i32) -> i32 {
        let s = s.chars().into_iter().collect::<Vec<_>>();
        let n = nums.len();
        let mut res = 0;
        const MOD: i64 = 1000000007;
        let mut arr = vec![];
        for i in 0..n {
            arr.push(if s[i] == 'L' {
                (nums[i] - d) as i64
            } else {
                (nums[i] + d) as i64
            })
        }
        arr.sort();
        for i in 1..n {
            let v = (arr[i] - arr[i - 1]) % MOD * ((n as i64) - i as i64) * (i as i64);
            res = (res + v) % MOD;
        }
        res as i32
    }
}