Problem: 2731. 移动机器人

前述条件

碰撞和1503. 所有蚂蚁掉下来前的最后一刻类似,注意到对于身份没有要求,所以可以直接认为两个机器人碰撞是交换了二者的身份,也可以认为是穿过去了
因此能够得到机器人的最终位置,为了方便计算,我们排序
数据量为$10^5$,暴力求解不现实
以下是三种常用的解决方法,这三种思路最开始的进入方式不同,但是都能得出正确结果

两种对于距离的计算方法

算法的时间复杂度均为$O(n)$

动态规划

思考方式与证明

假设已经计算出来了$a[i]$之前所有的机器人两两之间距离之和为$s$
增加一个元素$a[i]$,观察其和之前的所有机器人之间的距离之和,能够发现
1. 实际上就是与之前的每个元素计算距离
2. $a[i]$与$a[0],a[1]….,a[i-1]$之间的距离实际上分别是是$a[i-1]$与$a[0]….,a[i-1]$之间的距离加上$a[i]$与$a[i-1]$之间的距离,共$i$个
3. 上述结论可以推导: 设$distance[i]$表示$a[i]$和$a[0],a[1]….,a[i-1]$之间的距离之和,有 $$ distance[i]=i*a[i]+distance[i-1] \distance[0]=0 $$

代码

可以看出来这个公式只与前一个状态有关,因此可以优化空间

class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        mod=1000000007
        n=len(nums)
        for i,a in enumerate(s):
            nums[i]+=d if s[i]=='R' else -d  
        nums.sort()
        res=0
        distance=0
        for i in range(1,n):
            distance+=i*(nums[i]-nums[i-1]) 
            #这个方法对于只int的话4*(10**9)会超范围
            distance%=mod  
            res+=distance
        return res%mod

贡献距离法

思考方式

对于这种什么什么之和的问题可以考虑计算每个片段对结果的贡献
在这个题目之中片段就是每个元素之间的距离,我们需要计算的就是这段距离在结果中出现了多少次
为了方便理解将每次计算距离视为两点之间的连线,看片段上线的数目就知道这个片段的使用次数
从$a[0]-a[1]$这一的角度来看:从$a[0]$连出去了$n-1$条线,每条线都经过了$a[1]$,所以得出$a[0]-a[1]$段的贡献是$n-1$
从$a[1]-a[2]$的角度来看,$a[1]$连出去的$n-2$也就是$(n-i-1)$条线覆盖了$a[1]-a[2]$
1. 但还不够,注意到$a[0]$发出去的线只有一条落在了$a[1]$上,剩下的线也覆盖了$a[2]$
希望确切地知道此时到底有多少条线覆盖了这段距离

证明

设$f[i]$表示$a[i]$到$a[i+1]$这段距离对结果的贡献次数
同时可知$f[i]$也表示此时距离上面的线段数量
从a[i]发出的所有向右的线都会做贡献,这个次数为$n-i$
发现$a[i]$之前的线段,也就是参与了$f[i-1]$计算的线段,有一部分落在了$a[i]$上,剩下的部分继续参与$f[i]$的计算
可知落在$a[i]$上的线段实际上是a[i]发出的指向左边的线段,其数量为$i$
综上 $f[0]=n-i\f[i]=(f[i-1]-i+n)-i=f[i-1]-2*i+n$
$$\displaystyle res=\sum_{i=0}^{n-2}f[i]*(a[i+1]-a[i])$$

Code

可以看出只与前一个状态有关,进行空间优化代码为了方便对于$f[i]$计算的是$a[i+1]$到$a[i]$

class Solution:
  def sumDistance(self, nums: List[int], s: str, d: int) -> int:
      mod=1000000007
      n=len(nums)
      for i,a in enumerate(s):
          nums[i]+=d if s[i]=='R' else -d  
      nums.sort()
      pre=0
      res=0
      for i in range(n-1):
          pre=(pre+n-2*i-1)%mod
          res=(res+(nums[i+1]-nums[i])*pre)%mod
      return res

前缀和的形式化证明

下面是灵神的证明方式,与上面的证明相比更加数学,如下 $ (a[i]−a[0])+(a[i]−a[1])+⋯+(a[i]−a[i−1])=i⋅a[i]−(a[0]+a[1]+⋯+a[i−1])\$ $(a[0]+a[1]+⋯+a[i−1])$可根据前缀和求下面是灵神的代码

代码

class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        for i, c in enumerate(s):
            nums[i] += d if c == 'R' else -d
        nums.sort()
        ans = s = 0
        for i, x in enumerate(nums):
            ans += i * x - s
            s += x
        return ans % (10 ** 9 + 7)