第一题[编程题25分]：闹钟叫醒去上课 时间限制：C/C++1秒，其它语言2秒 空间限制：C/C++32768K，其它语言65536K 64bitIOFormat:% lld 题目描述： 小明总是睡过头，所以他定了很多闹钟，只有在闹钟响的时候他才会醒过来并且决定起不起来。 从他起床算起他需要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）分 数据保证至少有一个闹钟可以让牛牛及时到 达教室 输出描述： 输出两个整数表示牛牛最晚起床时间 示例1：（输入输出示例仅供调试，后台判题数据一般不包含示例） 输入： 3 50 60 70 59 659 输出： 60 思路一：创建一个时间对象，包含Hi和Mi，然后将闹钟时间封装成这个时间对象，然后将这些对象排序（快 排 时间复杂度为O（nlog2n）O（nlog_2n）O（nlog ? n）），然后就简单了，我开始是直接从结尾遍历，找到第一个满足条件的就输出（条件：闹钟时间+X<=上 课时间 ），然后终止，然而，并没有通过全部样例，清醒一下，想了一下，有序的序列，查找数据明摆着用 二分，就是查找一个序列中最右、最接近标杆的，比如一个序列 {1,2,3,3,3,4,10,10,11}，当标杆为3时， 我们应该要下标为5的那个3，当标杆为5时，我们应该要下标为6的那个4。 AC代码： importjava.util.ArrayList; importjava.utilparator; importjava.util.Scanner; publicclassMain{ publicstaticvoidmain(String[]args){ run (); } publicstaticvoidrun(){ Scannerscanner=newScanner(System.in); intN=scanner.nextInt();//闹钟数量 ArrayList<Time>list=newArrayList<>(); for(inti=0;i<N;++i){ list.add(newTime(scanner.nextInt(),scanner.nextInt()));//封装成Time对象 } list.sort(newComparator<Time>(){//将闹钟们排序 @Override publicintcompare(Timeo1,Timeo2){ returno1.hi-o2.hi==0?o1.mi-o2.mi:o1.hi- o2.hi; } }); intX=scanner.nextInt(),A=scanner.nextInt(),B=scanner.nextInt(); TimeAB=newTime(A,B);//上课时间 AB.jian(X); intl=0,r=list.size ()-1; while(l<=r){//二分搜索 intm=(l+r)>>1; if(ABpareTo(list.get(m))>=0){ l=m+1; }else{ r=m-1; } } if(r<0)//r可能小 于0，因为题目说了保证有解，那就输出第一个闹钟就可以了 System.out.println(list.get(0)); else System.out.println(list.get(r)); scanner.close (); } staticclassTimeimplementsComparable<Time>{//Time对象，实现Comparable接口，方便比较 inthi; intmi; publicTime(inthi,intmi) { this.hi=hi; this.mi=mi; } publicTimejian(intX){//时间的减法，6时30分-10分=6时20分 intT=hi*60+mi; intcha=T-X; hi=cha/60; mi=cha% 60; returnthis; } @Override publicintcompareTo(Timeo){ returnhi-o.hi==0?mi-o.mi:hi-o.hi;//按照小时升序，当小时相同时，按照分钟升序 } @Override publicStringtoString(){ returnhi+""+mi; } } } 思路二：由于上面创建了很多闹钟对象，比较费空间，所以我们可以将输入的 时间全部转换成分钟，比如6 时10分=6*60+10=370分，然后将输入的时间排序（快排时间复杂度为O（nlog2n）O（nlog_2n）O（nlog 2 ? n）），然后二分，思路和 上面一样。 AC代码： importjava.util.ArrayList; importjava.utilparator; importjava.util.Scanner; publicclassMain{ publicstaticvoidmain (String[]args){ run(); } publicstaticvoidrun(){ Scannerscanner=newScanner(System.in); intN=scanner.nextInt (); ArrayList<Integer>list=newArrayList<>(); for(inti=0;i<N;++i){ list.add(scanner.nextInt()*60+scanner.nextInt()); } list.sort(newComparator<Integer>(){ @Override publicintcompare(Integero1,Integero2){ returno1-o2; } }); intX=scanner.nextInt (); intA=scanner.nextInt(); intB=scanner.nextInt(); intAB=A*60+B;//上课时间，转换成了分钟 intt=AB-X;//这就是标杆 intl=0,r=list.size()- 1; while(l<=r){ intm=(l+r)>>1; if(t>=list.get(m)){ l=m+1; }else{ r=m-1; } } if(r<0) System.out.println(list.get (0)/60+""+list.get(0)%60); else System.out.println(list.get(r)/60+""+list.get(r)%60); scanner.close(); } } 第二题[编程 题25分]：秘密通信 时间限制：C/C++1秒，其它语言2秒 空间限制：C/C++32768K，其它语言65536K 64bitIOFormat:%lld 题目描述： 小明和安琪是好朋友。最近 ，他们的谈话被一家侦探机构监控，所以他们想将他们的谈话内容进行加密处。。。。。。以下内容略