十七 一共十七划

TAG

排序

2 篇文章

题解-移动机器人-数组计算的三种思考方式方式(动态规划,贡献,前缀和)与相关证明

Problem: 2731. 移动机器人 前述条件 碰撞和1503. 所有蚂蚁掉下来前的最后一刻类似,注意到对于身份没有要求,所以可以直接认为两个机器人碰撞是交换了二者的身份,也可以认为是穿过去了 因此能够得到机器人的最终位置,为了方便计算,我们排序 数据量为$10^5$,暴力求解不现实 以下是三种常用的解决方法,这三种思路最开始的进入方式不同,但是都能得出正确结果 两种对于距离的计算方法 算法的时间复杂度均为$O(n)$ 动态规划 思考方式与证明 假设已经计算出来了$a[i]$之前所有的机器人两两之间距离之和为$s$ 增加一个元素$a[i]$,观察其和之前的所有机器人之间的距离之和,能够发现 实际上就是与之前的每个元素计算距离 $a[i]$与$a[0],a[1]….,a[i-1]$之间的距离实际上分别是是$a[i-1]$与$a[0]….,a[i-1]$之间的距离加上$a[i]$与$a[i-1]$之间的距离,共$i$个 上述结论可以推导: 设$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]$ 但还不够,注意到$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])$可根据前缀和求 下面是灵神的代码

↗