[每日一题] 2731. 移动机器人 (思维 + 前面元素所有差值求和)

class Solution {
public:
    // 这道题碰撞了，其实和不碰撞是一样的，因为
    // 碰撞之前，一个向左，一个向右，但是碰后，还是一个左，一个右，速度都没变
    int sumDistance(vector<int>& nums, string s, int d) {
        // 不考虑碰撞，每个机器人直接走
        for(int i = 0; i < s.size(); i ++) {
            if(s[i] == 'R') {
                nums[i] = nums[i] + d;
            }
            else {
                nums[i] = nums[i] - d;
            }
        }

        // 计算距离
        // 计算距离这里，如果用两个for去算，就会TLE
        sort(nums.begin(), nums.end());
        
        for(auto it : nums) cout << it << " ";
        cout << endl;
        
        long long ans = 0;
        long long sum = 0;
        const int mod = 1e9 + 7;

        /* 
           这个地方非常巧妙
           现在我要计算 nums[0] 到 nums[i] 中的所有的元素的差值
           实际上，就是每个元素与他前面所有的元素的差的和，那么对于第i个元素则有
           (nums[i] - nums[0]) + (nums[i] - nums[1]) + ..... + (nums[i] - nums[i - 1])
           通过数学变换则有：
           i * nums[i]  - (nums[0] + nums[1] + ...nums[i - 1])
           因此可以用sum来迭代记录 nums[i - 1] 到 nums[0] 的值
        */ 

        for (int i = 0; i < nums.size(); ++i) {
            ans = (ans + i * (long long)nums[i] - sum) % mod;
            sum += nums[i];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43