力扣(LeetCode)2731. 移动机器人(C++)

脑经急转弯+排序

碰撞只改变运动方向，速度始终如"1"，且机器人视为无差别的，所以碰撞等于擦肩而过！"机器人碰撞，到底撞没撞，如撞。"因此只考虑每个机器人单方向移动，d秒后停下，即可。

统计所有机器人之间两两距离之和，可以按照贡献法：
一共n个点(机器人)，有n-1个间隔(相邻机器人的间距)，$每个间隔被统计的次数=左侧的点的数量(包含端点)\ast 右侧的点的数量(包含端点)$

排序后，按照贡献法(其实是数学方法hh)统计距离之和，得到答案，本题解决。

class Solution {
public:
    const int mod = 1e9 + 7;
    int sumDistance(vector<int>& nums, string s, int d) {
        for (int i = 0; i < nums.size(); i ++) {
            if ('L' == s[i]) {
                nums[i] -= d;
            } else {
                nums[i] += d;
            }
        }
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 1; i < nums.size(); i ++) {
            long long t = ((long long)nums[i]  - (long long)nums[i - 1]) % mod * (i * (nums.size() - i) % mod);
            ans = (ans + t) % mod;
        }
        return ans;
    }
};
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度 $O(nlogn)$ : $n$是$nums$的长度(机器人的数量)，排序的时间复杂度$O(nlogn)$。
空间复杂度 $O(n)$ : 本文原地修改数组，空间瓶颈取决于排序的空间复杂度$O(logn)$。建议另开一个数组存储机器人的位置，空间复杂度 $O(n)$ 。

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。