Acwing算法心得——猜测短跑队员的速度（重写比较器）

大家好，我是晴天学长，今天的算法题用到了比较器的知识，是经常会用到的一个知识点，常见与同种数据的排序，需要的小伙伴请自取哦！如果觉得写的不错的话，可以点个关注哦，后续会继续更新的。💪💪💪

---

1 ）猜测短跑队员的速度

一个短跑运动员在一个数轴上跑步。 他的奔跑速度是恒定的，但是奔跑方向可能会不断发生改变，有时朝数轴正方向，有时朝数轴负方向。 给定 N 个不同时刻下他所在的位置，请你计算他的速度至少是多少。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含两个整数 T 和 X，表示时刻 T 时，运动员位于位置 X。

注意，输入时刻两两不同，但是不一定按时间顺序给出。

输出格式
一个实数，表示运动员的最小可能速度。

输出结果与标准答案的相对误差小于 10−5 即视为正确。
数据范围
2≤N≤105, 0≤T≤109, −109≤X≤109
输入样例1：
3 0 100 20 50 10 120
输出样例1：
7.0
样例1解释
运动员时刻 0 在位置 100，10 秒后，他位于位置 120，由此可知，他的速度一定不低于 (120−100)/10=2，又过了 10 秒，他位于位置 50，由此可知，它的速度一定不低于 (120−50)/10=7。

输入样例2：
5 20 -5 0 -17 10 31 5 -3 30 11
输出样例2：
6.8

---

2) .算法思路

答案中的代码是这样的，假设需要排序的数组intervals：

int[][] intervals = {{2,3},{2,9},{4,5},{3,7},{6,7},{8,9},{1,10}};
Arrays.sort(intervals, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        if(o1[0]==o2[0]){
            return o1[1] - o2[1];
        }
        return o1[0] - o2[0];
    }
});
1
2
3
4
5
6
7
8
9
10

此代码中，对于每个o1和o2数组，若各自第一个元素（也就是o1[0]和o2[0]）相等，则按照各自第二个元素进行升序比较，否则就按照第一个元素进行升序比较。

在此，o1[0] - o2[0] 表示升序，o2[0] - o1[0] 表示降序。

比如这个代码，结果如下：

1 10
2 3
2 9
3 7
4 5
6 7
8 9
o1[0]表示第一个元素，以此类推，所以我们想要根据第几个元素排序，就写入就好：

// 按照第三个元素排序
int[][] intervals = {{2,3,4,5},{2,9,7,5},{4,5,1,5},{3,7,1,2},{6,7,3,4}};
Arrays.sort(intervals, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[2] - o2[2];
    }
});
1
2
3
4
5
6
7
8

得到的结果如下：

4 5 1 5
3 7 1 2
6 7 3 4
2 3 4 5
2 9 7 5
另外，他还有其他的写法：

• 使用Lambda表达式的方式对Comparator比较器进行简写（JDK1.8+）

int[][] intervals = {{2,3,4,5},{2,9,7,3},{4,5,1,5},{3,7,1,2},{6,7,3,4}};
Arrays.sort(intervals, (o1, o2) -> {
    return o1[2] - o2[2];
});
1
2
3
4

---

3）. 算法步骤

1.导入需要使用的类：Arrays、Comparator和Scanner。
2.创建一个Main类，作为程序的入口点。
3.创建一个Scanner对象，用于读取输入。
4.从输入中读取一个整数N，表示搜索数据的数量。
5.创建一个二维数组search，大小为N×2，用于存储搜索数据。
6.使用循环，读取N个搜索数据，并将它们存储在search数组中。
7.使用Arrays.sort方法对search数组进行排序，根据每个搜索数据的第一个元素进行升序排序。
8.通过创建一个Comparator对象，重写compare方法，指定按照第一个元素的升序排序。
9.或者使用lambda表达式 (o1, o2) -> (o1[0] - o2[0]) 作为排序的比较函数。
10.初始化一个变量min为0，用于存储最大搜索斜率的初始值。
11.使用循环，从数组的第二个元素开始，遍历所有搜索数据。
12.计算两个搜索数据之间的斜率，即当前搜索数据的纵坐标与前一个搜索数据的纵坐标之差除以横坐标的差值。
13.更新min的值，取当前斜率与min的较大值。
14使用System.out.format方法，以保留一位小数的格式输出min的值。
15.程序执行完毕。

---

4）.代码示例

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int [][] search =  new int[N][2];
        for (int i = 0; i < N; i++) {
            search[i][0] = scanner.nextInt();
            search[i][1] = scanner.nextInt();
        }
        //重写排序
//        Arrays.sort(search, (o1, o2) -> (o1[0] - o2[0]));
        Arrays.sort(search,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
               return o1[0] - o2[0];
            }
        });
            double min = 0;
            for (int i = 1; i < N; i++) {
                double x = Math.abs(search[i][1] - search[i-1][1]);
                double t = search[i][0] - search[i - 1][0];
                min = Math.max(min, x / t);
            }
        System.out.format("%.1f", min);
    }
}

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

---

5）.总结

• 排序的重写器。

---

试题链接：