原题链接:
https://leetcode.cn/problems/movement-of-robots

解法1:

脑筋急转弯 + 排序统计
还要注意一下溢出问题 算是这题比较坑的地方

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
/**
    1. 题目要求的是机器人之间的距离 与顺序无关 -> 那么把机器人位置交换 并不会对答案产生影响 
    2. 相撞可视为互相穿过对方 -> 可以无视相撞规则 把每个机器人堪称独立运动 
    3. 由于要计算的是每一对机器人之间的距离 所以先对运动后的机器人位置进行排序
       从小到大 枚举 对于第i个数 a[i] 其与前i个数的距离为
       (a[i] - a[i - 1]) + (a[i] - a[i - 2]) + ... + (a[i] - a[0]) 
       = i * a[i] - (a[i - 1] + a[i - 2] + ... + a[0]) 
 */
class Solution {
    private static final long MOD = (long)(1e9 + 7);
    public int sumDistance(int[] nums, String s, int d) {
        int n = nums.length;
        // 数组也要建一个新的 因为 nums[i] + d可能溢出
        long [] a = new long [n];
        for(int i  = 0 ; i < n ; i++){
            if(s.charAt(i) == 'L'){
                a[i] = nums[i] - d;
            }else{
                a[i] = nums[i] + d;
            }
        }
        long ans = 0;
        Arrays.sort(a);
        // 记录前i个数之和
        long pre = a[0];
        for(int i = 1 ; i < n ; i++){
            // 计算的是 两两之间的距离 所以每一对机器人之间的距离都要计算过一次
            // 要乘一个i
            ans =  (ans + i * a[i] - pre) % MOD;
            pre = (pre + a[i]) % MOD;
        }

        return (int)ans;
    }
}