《从入门到精通：蓝桥杯编程大赛知识点全攻略》（十二）-航班时间、日志统计、献给阿尔吉侬的花束

前言

在本篇博客中，我们将深入探讨三种经典的算法问题：航班时间问题、日志统计问题以及“献给阿尔吉侬的花束”问题。每个问题的解决方案都采用了不同的算法技巧，帮助我们在复杂问题中找到高效的解法。我们将首先介绍每个问题的背景和挑战，然后带领大家一步步走过如何运用双指针、广度优先搜索等算法来解决这些问题。无论你是算法初学者还是有经验的开发者，相信这些案例都能为你的算法思维带来启发。

航班时间

小 h 前往美国参加了蓝桥杯国际赛。
小 h的女朋友发现小 h上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。
小 h 对超音速飞行感到十分恐惧。
仔细观察后发现飞机的起降时间都是当地时间。
由于北京和美国东部有 12 小时时差，故飞机总共需要 14 小时的飞行时间。
不久后小 h 的女朋友去中东交换。
小 h 并不知道中东与北京的时差。
但是小 h 得到了女朋友来回航班的起降时间。
小 h 想知道女朋友的航班飞行时间是多少。
对于一个可能跨时区的航班，给定来回程的起降时间。
假设飞机来回飞行时间相同，求飞机的飞行时间。
输入格式
一个输入包含多组数据。
输入第一行为一个正整数 T，表示输入数据组数。
每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。
起降时间的格式如下:

h1:m1:s1 h2:m2:s2
h1:m1:s1 h3:m3:s3 (+1)
h1:m1:s1 h4:m4:s4 (+2)

第一种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间当日h2时m2分s2秒降落。
第二种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间次日h2时m2分s2秒降落。
第三种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间第三日h2时m2分s2秒降落。
输出格式
对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。
注意，当时间为一位数时，要补齐前导零，如三小时四分五秒应写为03:04:05。
数据范围
保证输入时间合法（0≤h≤23,0≤m,s≤59），飞行时间不超过24小时。
输入样例：

3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)

输出样例：

04:09:05
12:10:39
14:22:05

算法思路

在这里插入图片描述
去时所用的飞行时间是相差+时差，返程所用的飞行时间是相差-时差，故往返来程 = 2 * 飞行时间 = 2 * 相差，故（end2-begin1 + end1 - begin1） / 2 = 飞行时间。计算时将对应的时间全部都转化为秒来计算即get_second函数；同时这道题麻烦的是输入时间相减时还要注意加上天数。最后再同意换成时分秒即可得到最后的答案。

代码如下


import java.io.*;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);public static void main(String[] args)throws Exception {int n = Integer.parseInt(br.readLine());while(n-- > 0 ){int time=(get_time()+get_time())/2;int hour=time/3600;int minute=time%3600/60;int secound=time%60;pw.printf("%02d:%02d:%02d\n", hour,minute,secound);}pw.flush();}public static int get_time() throws Exception{String str=nextLine();int day=0;if(str.charAt(str.length()-1)==')'){day=Integer.parseInt(""+str.charAt(str.length()-2));str=str.substring(0, str.length()-5);}String s[]=str.split(" ");String s1[]=s[0].split(":");String s2[]=s[1].split(":");int a1=Integer.parseInt(s1[0]);int a2=Integer.parseInt(s1[1]);int a3=Integer.parseInt(s1[2]);int b1=Integer.parseInt(s2[0]);int b2=Integer.parseInt(s2[1]);int b3=Integer.parseInt(s2[2]);return  get_second(b1, b2, b3)-get_second(a1, a2, a3)+day*24*3600;}public static int get_second(int h,int m,int s){return 3600*h+m*60+s;}public static String nextLine()throws Exception{return br.readLine();}}

日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：

ts id

表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K。
以下 N行每行一条日志，包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围
1≤K≤N≤10⁵,
0≤ts,id≤10⁵,
1≤D≤10000
输入样例：

输出样例：

1
3

算法思路

在这里插入图片描述
整型数组cnt[i]表示帖子id为i所获得的赞的个数
布尔类型数组flag[i]表示日志id为i的帖子是热帖
将日志信息存储在blogs数组中，并且按照时间顺序排序。然后枚举每一个日志，循环i表示区间的结尾，j表示区间的开头，记录一下id = blogs[i].id；然后将对应的赞个数加1即，同此进行一个循环当blogs[i].ts - blogs[j].ts >= d时即此时已经到达时间区间长度的最大值，开头减去即cnt[blogs[j].id]–;同时区间开头右移j++；再进行判断如果赞大于等于k说明是热帖即flag[id] = true；最后再将flag数组中为true的热帖打印即可。

代码如下

package AcWingLanQiao;import java.io.*;
import java.util.Arrays;public class 日志统计 {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int n,d,k;static int[] cnt = new int[N];static blog[] blogs = new blog[N];static boolean[] flag = new boolean[N];//记录每个帖子是否是热帖public static void main(String[] args)throws Exception {n = nextInt();d = nextInt();k = nextInt();for(int i = 0; i < n;i++){blogs[i] = new blog();blogs[i].ts = nextInt();blogs[i].id = nextInt();}Arrays.sort(blogs,0,n);for(int i = 0,j = 0;i < n;i++){int id = blogs[i].id;cnt[id]++;while(blogs[i].ts - blogs[j].ts >= d){cnt[blogs[j].id]--;j++;}if(cnt[id] >= k){flag[id] = true;}}for(int i = 0;i <= 100000;i++){if(flag[i]){pw.println(i);}}pw.flush();}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}
}class blog implements Comparable<blog>{int ts;int id;//按照时间升序排列@Overridepublic int compareTo(blog blog) {if(this.ts == blog.ts){return this.id-blog.id;}return this.ts - blog.ts;}
}

bfs

建一个队列 queue，并将起始节点加入队列。

创建一个 visited 集合，记录已访问的节点。

访问节点：

当队列不为空时：
- 从队列中取出一个节点。
- 处理该节点（例如输出节点信息）。
- 将该节点的所有未访问过的邻接节点加入队列，并标记为已访问。

结束条件：

队列为空时，BFS 完成。

献给阿尔吉侬的花束

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
输入格式
第一行是一个正整数 T，表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R和 C，表示地图是一个 R×C
的矩阵。
接下来的 R行描述了地图的具体内容，每一行包含了 C个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。
每组数据的输出结果占一行。
数据范围
1<T≤10,
2≤R,C≤200
输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例：

5
1
oop!

算法思路

在这里插入图片描述

遍历地图，找到起点 ‘S’ 和终点 ‘E’ 的坐标，并将其存储在 start 和 end 对象中。
BFS 搜索：

初始化一个队列 q 用来存储当前节点，使用二维数组 step 来记录每个位置到起点的最短步数，初始时所有位置的步数设为 -1（表示未访问）。
将起点的步数设置为 0，并将起点入队。

BFS 扩展：
-从队列中取出当前节点，检查其四个邻居（上下左右）。对每个邻居：

如果邻居超出边界、是障碍物或者已经访问过，则跳过。
否则，将该邻居的步数设置为当前节点步数 + 1，并将该邻居加入队列。
如果找到终点，立即返回当前步数。

结果处理：

如果在 BFS 搜索中找到了终点，返回最短路径长度。
如果无法到达终点，返回 -1，并输出 “oop!”。

处理多个测试用例：

每个测试用例结束后，重置 step 数组，以便处理下一个测试用例。

代码如下


import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static char[][] map = new char[210][210];static int[][] step = new int[210][210];static int n,m;static Queue<Pair> q = new LinkedList<>();public static void main(String[] args) throws Exception{int T = Integer.parseInt(br.readLine());while(T-->0){String[] str = br.readLine().split(" ");n = Integer.parseInt(str[0]);m = Integer.parseInt(str[1]);for(int i = 0; i < n; i++){map[i] = br.readLine().toCharArray();}Pair start = null;Pair end = null;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(map[i][j] == 'S'){start = new Pair(i, j);}else if(map[i][j] == 'E'){end = new Pair(i, j);}}}int distance = bfs(start, end);if(distance == -1){pw.println("oop!");}else {pw.println(distance);}}pw.flush();}public static int bfs(Pair start,Pair end){Queue<Pair> q = new LinkedList<>();for (int i = 0; i < n; i++) {Arrays.fill(step[i], -1);}step[start.x][start.y] = 0;q.add(start);while(!q.isEmpty()){Pair p = q.poll();//上下左右int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};for(int i = 0;i < 4;i++){int x = p.x + dx[i];int y = p.y + dy[i];if(x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '#' || step[x][y] != -1) continue; //出界、障碍物、已经走过step[x][y] = step[p.x][p.y] + 1;if(end.x == x && end.y == y){return step[x][y];}q.add(new Pair(x, y));}}return -1;}public static String nextLine()throws Exception{return br.readLine();}static class Pair{int x;int y;public Pair(){}public Pair(int x, int y){this.x = x;this.y = y;}}
}

总结

通过本篇博客中的三个算法问题，我们不仅复习了常见的算法技巧，如双指针法和广度优先搜索，还通过实际问题展示了它们在实际应用中的强大威力。在航班时间问题中，双指针法帮助我们优化了复杂的时间区间查找；在日志统计问题中，双指针也有效解决了数据整理和筛选问题；而在“献给阿尔吉侬的花束”问题中，广度优先搜索为我们提供了最短路径的解决方案。希望通过这些算法问题的讲解，大家能够更好地理解并掌握这些常用的算法思维，为以后解决更复杂的技术问题打下基础。