【力扣每日一题】2023.10.10 移动机器人

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目比较复杂，我概括一下。给我们一个数组表示不同机器人在一维坐标轴上的初始位置，还有一个字符串表示每个机器人的初始移动方向。当两个机器人相撞时（处于同一坐标）或者即将相撞时（坐标相邻），两个机器人的移动方向都立刻改变。

每秒机器人都移动一格，问最后机器人两两之间的距离之和一共是多少。

要解决这道题，我们要先解决两个问题，第一个就是机器人的移动问题，关于机器人的碰撞我们应该怎么处理。第二个就是机器人两两之间的距离怎么快速计算，直接套两层for循环去计算是会超时的。

第一个就是碰撞处理，直接模拟的话，效果是像下面这个动图的。

上面动图的意思是一开始机器人1右走，机器人2左走，相遇之后机器人1改为左走，机器人2改为右走，如果是像这样模拟的话，每秒我们都需要将每个机器人都移动一次再进一步判断是否改方向，这样也是会超时的。

关于碰撞处理，最好的处理方式是不做任何处理。

如上动图我们可以知道，不做任何处理，并且我们不再区分机器人，在移动之后得到的坐标和最初做了碰撞处理之后的结果是一样的。

所以面对第一个问题，我们直接不处理碰撞，直接把机器人的初始坐标加上对应方向的移动秒数即可。

第二个问题就是计算两两机器人之间的距离差。

我们先把机器人最终的坐标都摊在坐标轴上观察，机器人和别的机器人的距离我用不同颜色标出。

可以看的出来，机器人两两之间的距离有很多是重叠的，我们在把相邻机器人之间的重复距离段给提取出来。

我们可以找出规律，第i个机器人到第i+1个机器人之间的距离段一共重复了（ i *（ len - i ）），i 从1开始。例如第一个机器人和第二个机器人之间的距离段一共重复了 1*（5-1）也就是4次。

两个问题都解决之后我们就知道应该怎么做了。首先先直接移动每个机器人，如果是右走，那么就直接在坐标加上秒数，如果是左走，那么坐标就减去秒数。

移动完毕就开始排序，因为我们上述的做法需要保证机器人在坐标上是有序的。

接着计算出机器人两两之间的距离就按照我们上面的式子，只需要遍历一次即可，由于数值较大，所以我们需要对答案进行取余。

代码：

class Solution {
public:
    int sumDistance(vector<int>& nums, string s, int d) {
        long long res=0;
        for(int i=0;isize();++i){
            if(s[i]=='R') nums[i]+=d;
            else nums[i]-=d;
        }
        sort(nums.begin(),nums.end());
        for(int i=1;isize();++i){
            res+=(static_cast<long long>(nums[i])-nums[i-1])*i*(nums.size()-i)%1000000007;
        }
        return res%1000000007;
    }
};