这是一道牛客网上的编程题。
1 题目描述
牛牛总是睡过头，所以他定了很多闹钟，只有在闹钟响的时候他才会醒过来并且决定起不起床。从他起床算起他需要X分钟到达教室，上课时间为当天的A时B分，请问他最晚可以什么时间起床。
-
输入描述
每个输入包含一个测试用例。 每个测试用例的第一行包含一个正整数，表示闹钟的数量N(N<=100)。 接下来的N行每行包含两个整数，表示这个闹钟响起的时间为Hi(0<=A<24)时Mi(0<=B<60)分。 接下来的一行包含一个整数，表示从起床算起他需要X(0<=X<=100)分钟到达教室。 接下来的一行包含两个整数，表示上课时间为A(0<=A<24)时B(0<=B<60)分。 数据保证至少有一个闹钟可以让牛牛及时到达教室。
-
输出描述
输出两个整数表示牛牛最晚起床时间。
-
示例
输入
3 5 0 6 0 7 0 59 6 59
输出
6 0
2 思路
- 先将所有的闹钟时间按照从早到晚排序。
- 通过上课时间和赶路时间计算出最晚起床时间。
- 用二分查找在所有闹钟时间中找最晚起床时间，如果找到则直接输出，如果没找到就输出插入位置前一个闹钟。
3 代码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
Integer[][] alarms = new Integer[N][2];
for (int i = 0; i < N; ++i) {
alarms[i][0] = scanner.nextInt();
alarms[i][1] = scanner.nextInt();
}
// 对闹钟进行排序
Arrays.sort(alarms, (Integer[] a1, Integer[] a2)->{
// 如果时不相等就返回时的比较结果
if (a1[0].compareTo(a2[0]) != 0) {
return a1[0].compareTo(a2[0]);
} else {
// 否则返回分的比较结果
return a1[1].compareTo(a2[1]);
}
});
int X = scanner.nextInt();
int A = scanner.nextInt();
int B = scanner.nextInt();
// 算出最晚起床时间
A -= X / 60;
X %= 60;
if (B >= X) {
B -= X;
} else {
--A;
B = B + 60 - X;
}
Integer[] getUp = {A, B};
// 用二分查找在所有闹钟时间中查找起床时间
int result = Arrays.binarySearch(alarms, getUp, (Integer[] a1, Integer[] a2)->{
// 如果时不相等就返回时的比较结果
if (a1[0].compareTo(a2[0]) != 0) {
return a1[0].compareTo(a2[0]);
} else {
// 否则返回分的比较结果
return a1[1].compareTo(a2[1]);
}
});
// 如果正好找到就输出此闹钟
if (result >= 0) {
System.out.println(alarms[result][0] + " " + alarms[result][1]);
} else {
// 如果没有恰好相等的，返回的是恰好大于起床时间的那个闹钟的 - index - 1，
// 所以要输出 - result - 2 位置的闹钟。
System.out.println(alarms[- result - 2][0] + " " + alarms[- result - 2][1]);
}
}
}