力扣(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;}
};
};

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

AC

致语

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