问题简化
给你$n$个数,求任意两对下标之间的子段和(求任意两数差值之和
题目描述
有一些机器人分布在一条无限长的数轴上,每个机器人初始方向只有’$L$’,’$R$’两种,每秒钟移动一次,记录在$S$字符串中。当两个机器人相撞时,它们开始沿着原本相反的方向移动。 求$d$ 秒后,所有机器人之间两两距离之和
n $\le$ $1e5$
样例
示例 1:
输入:nums = [-2,0,2], s = "RLL", d = 3
输出:8
解释:
1 秒后,机器人的位置为 [-1,-1,1] 。现在下标为 0 的机器人开始往左移动,下标为 1 的机器人开始往右移动。
2 秒后,机器人的位置为 [-2,0,0] 。现在下标为 1 的机器人开始往左移动,下标为 2 的机器人开始往右移动。
3 秒后,机器人的位置为 [-3,-1,1] 。
下标为 0 和 1 的机器人之间距离为 abs(-3 - (-1)) = 2 。
下标为 0 和 2 的机器人之间的距离为 abs(-3 - 1) = 4 。
下标为 1 和 2 的机器人之间的距离为 abs(-1 - 1) = 2 。
所有机器人对之间的总距离为 2 + 4 + 2 = 8 。
示例 2:
输入:nums = [1,0], s = "RL", d = 2
输出:5
解释:
1 秒后,机器人的位置为 [2,-1] 。
2 秒后,机器人的位置为 [3,-2] 。
两个机器人的距离为 abs(-2 - 3) = 5 。
算法1
时间复杂度
参考文献
C++ 代码
写法一:思维,推理
const int mod = 1e9+7;
class Solution {
public:
int sumDistance(vector<int>& nums, string s, int d) {
vector<long long> v;
int n=nums.size();
for(int i=0;i<n;i++){
if(s[i]=='R') v.push_back((long long)nums[i]+d);
else v.push_back((long long)nums[i]-d);
}
sort(v.begin(),v.end());
int ans=0;
for(int i=1;i<n;i++){
ans+=1ll*(v[i]-v[i-1])*i%mod*(n-i)%mod;
ans%=mod;
}
return ans;
}
};
写法二:(前缀和) $O(n)$
class Solution {
public:
static const int MOD = 1e9 + 7;
int sumDistance(vector<int>& nums, string s, int d) {
int n = nums.size();
vector<int64_t> pos(n);
for (int i = 0; i < n; ++i) {
pos[i] = (int64_t)nums[i] + (s[i] == 'L' ? -d : d);
}
ranges::sort(pos);
int64_t ans = 0, sum = 0;
for (int i = 0; i < n; ++i) {
ans = (ans + pos[i] * i - sum) % MOD;
sum += pos[i];
}
return ans;
}
};
クトリ