前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第八讲：枚举与模拟【习题】
本篇博客所包含习题有：
👊移动距离
👊日期问题
👊航班时间
👊外卖店优先级
枚举与模拟【例题】见博客：蓝桥杯第八讲–枚举与模拟【例题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
移动距离
来源： 第六届蓝桥杯省赛C++B组,第六届蓝桥杯省赛JAVAA/C组
题目要求
题目描述：
X星球居民小区的楼房全是一样的，并且按矩阵样式排列。
其楼房的编号为 1 , 2 , 3 …
当排满一行时，从下一行相邻的楼往反方向排号。
比如：当小区排号宽度为 6 时，开始情形如下：
1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 …
我们的问题是：已知了两个楼号 m 和 n ，需要求出它们之间的最短移动距离（不能斜线方向移动）。
输入格式：
输入共一行，包含三个整数w , m , n w,为排号宽度，m , n 为待计算的楼号。
数据范围：
1≤w,m,n≤10000,
输入样例：
6 8 2
输出样例：
4
思路分析
一道相对来说比较基础的模拟题，但还是需要一些简单的处理，我们的数组是从 0 行 0 列开始的，但是我们这里下标是从 1开始的，为了方便处理，我们可以让所有的下标全部-1，这里是求距离，在算法题中，我们一般有两个距离：
- 曼哈顿距离：两个点的折线距离
- 欧式距离：两个点的连线距离
本题求的其实就是曼哈顿距离，即我们需要知道两个点分别的纵坐标和横坐标，然后输出 abs(x1 - x2) + abs(y1 - y2) 即可，把下标换为坐标：横坐标为：/ w ，纵坐标为：% w ，如果是奇数行（行和列均从 0 开始），则需要翻转一下列，即：y = w - 1 - y
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { int w, m, n; cin >> w >> m >> n; m --, n --; int x1 = m / w, x2 = n / w; int y1 = m % w, y2 = n % w; if (x1 % 2) y1 = w - 1 - y1; if (x2 % 2) y2 = w - 1 - y2; cout << abs(x1 - x2) + abs(y1 - y2) << endl; return 0; }
日期问题
来源： 第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组
题目要求
题目描述：
小明正在整理一批历史文献。这些历史文献中出现了很多日期。
小明知道这些日期都在1960 年1 11月1 日至2059 年12 月31 日。
令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。
更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。
比如02 / 03 / 04 ，可能是2002 年03 月04 日、2004年02月03 日或2004 年03月02日。
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
输入格式：
一个日期，格式是" A A / B B / C C "。
即每个’ / ’隔开的部分由两个 0 − 9 之间的数字（不一定相同）组成。
输出格式：
输出若干个不相同的日期，每个日期一行，格式是" y y y y − M M − d d " 。
多个日期按从早到晚排列。
数据范围：
0≤A,B,C≤9
输入样例：
02/03/04
输出样例：
2002-03-04
2004-02-03
2004-03-02
思路分析
本题提供两个代码，一个是纯粹的模拟（思路简单，按照题目要求即可），代码量比较长，另一个是一个方便的处理手段，类似在：蓝桥杯第八讲–枚举与模拟【例题】 中的 回文日期，下面对于思路分析只介绍第二种，纯模拟代码不做解释
对于优化而言其实就是如同 回文日期 中的枚举法，把日期当做一个八位数进行 f o r 枚举，对于每个日期首先需要判断其的合法性，即 i s _ r i g h t 函数，进而进行进一步的比对。
代码（纯模拟）
#include <iostream> #include <cstring> #include <algorithm> #include <string> #include <map> #include <set> using namespace std; map<string, int> mon; set<string> res; void add(string year, string month, string day) { string temp = year + '-' + month + '-' + day; res.insert(temp); } int is_leap(string u) { int year = 0; for (int i = 0; i < 4; i ++ ) year = year * 10 + (u[i] - '0'); return (!(year % 400) || (year % 100) && !(year % 4)); } int num(string u) { int day = 0; for (int i = 0; i < 2; i ++ ) day = day * 10 + (u[i] - '0'); return day; } void get_right(string year, string month, string day) { if (year >= "1960" && year <= "2059") { // 不是2月 if (month >= "01" && month <= "12" && month != "02") if (day >= "01" && num(day) <= mon[month]) add(year, month, day); // 是2月且是闰年 if (month == "02" && is_leap(year)) if (day >= "01" && num(day) <= mon["02"] + 1) add(year, month, day); // 是2月但不是闰年 if (month == "02" && !is_leap(year)) if (day >= "01" && num(day) <= mon["02"]) add(year, month, day); } } int main() { //月份到天数的映射 mon["01"] = 31, mon["02"] = 28, mon["03"] = 31, mon["04"] = 30, mon["05"] = 31, mon["06"] = 30, mon["07"] = 31, mon["08"] = 31, mon["09"] = 30, mon["10"] = 31, mon["11"] = 30, mon["12"] = 31; string s; cin >> s; //把三个数以字符串(因为有前导0)的形式给取出来: string s1, s2, s3; for (int i = 0; i < 2; i ++ ) s1 += s[i]; for (int i = 3; i < 5; i ++ ) s2 += s[i]; for (int i = 6; i < 8; i ++ ) s3 += s[i]; //写成:年/月/日的形式 get_right("19" + s1, s2, s3); get_right("20" + s1, s2, s3); //写成:月/日/年的形式 get_right("19" + s3, s1, s2); get_right("20" + s3, s1, s2); //写成:日/月/年的形式 get_right("19" + s3, s2, s1); get_right("20" + s3, s2, s1); for (auto it = res.begin(); it != res.end(); it ++ ) cout << *it << endl; return 0; }
代码（思维优化）
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int mon[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool is_right(int year, int month, int day) { if (month == 0 || month > 12) return false; if (day == 0) return false; if (month != 2 && day > mon[month]) return false; int leap = !(year % 400) || year % 100 && !(year % 4); if (month == 2 && day > mon[2] + leap) return false; return true; } int main() { int a, b, c; scanf("%d/%d/%d", &a, &b, &c); for (int i = 19600101; i <= 20591231; i ++ ) { int year = i / 10000; int month = i % 10000 / 100; int day = i % 100; if (is_right(year, month, day)) { if (year % 100 == a && month == b && day == c || // 年/月/日 month == a && day == b && year % 100 == c || // 月/日/年 day == a && month == b && year % 100 == c // 日/月/年 ) printf("%d-%02d-%02d\n", year, month, day); } } return 0; }
