前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第八讲：枚举与模拟【习题】

本篇博客所包含习题有：
👊移动距离
👊日期问题
👊航班时间
👊外卖店优先级

枚举与模拟【例题】见博客：蓝桥杯第八讲–枚举与模拟【例题】

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

移动距离

来源： 第六届蓝桥杯省赛C++B组,第六届蓝桥杯省赛JAVAA/C组

题目要求

题目描述：

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。

其楼房的编号为 $1,2,3\dots$

当排满一行时，从下一行相邻的楼往反方向排号。

比如：当小区排号宽度为 $6$ 时，开始情形如下：

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 …

我们的问题是：已知了两个楼号 $m$ 和 $n$，需要求出它们之间的最短移动距离（不能斜线方向移动）。

输入格式：

输入共一行，包含三个整数 $w,m,n$，$w$ 为排号宽度，$m,n$ 为待计算的楼号。

输出格式：

输出一个整数，表示 $m,n$ 两楼间最短移动距离。

数据范围：

$1\le w,m,n\le 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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

日期问题

来源： 第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组

题目要求

题目描述：

小明正在整理一批历史文献。这些历史文献中出现了很多日期。

小明知道这些日期都在$1960$年$1$月$1$日至$2059$年$12$月$31$日。

令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。

更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如$02/03/04$，可能是$2002$年$03$月$04$日、$2004$年$02$月$03$日或$2004$年$03$月$02$日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式：

一个日期，格式是$"AA/BB/CC"$。

即每个$’/’$隔开的部分由两个 $0-9$ 之间的数字（不一定相同）组成。

输出格式：

输出若干个不相同的日期，每个日期一行，格式是$"yyyy-MM-dd"$。

多个日期按从早到晚排列。

数据范围：

$0\le A,B,C\le 9$

输入样例：

02/03/04

输出样例：

2002-03-04
2004-02-03
2004-03-02

思路分析

本题提供两个代码，一个是纯粹的模拟（思路简单，按照题目要求即可），代码量比较长，另一个是一个方便的处理手段，类似在：蓝桥杯第八讲–枚举与模拟【例题】 中的 回文日期，下面对于思路分析只介绍第二种，纯模拟代码不做解释

对于优化而言其实就是如同 回文日期 中的枚举法，把日期当做一个八位数进行 $for$ 枚举，对于每个日期首先需要判断其的合法性，即 $is\_right$ 函数，进而进行进一步的比对。

代码（纯模拟）

#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;
}

  

 

  
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
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
 

代码（思维优化）

#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;
}

  

 

  
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
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
 

航班时间

来源： 第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组

题目要求

题目描述：

小 $h$ 前往美国参加了蓝桥杯国际赛。

小 $h$ 的女朋友发现小 $h$ 上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。

小 $h$ 对超音速飞行感到十分恐惧。

仔细观察后发现飞机的起降时间都是当地时间。

由于北京和美国东部有 $12$ 小时时差，故飞机总共需要 $14$ 小时的飞行时间。

不久后小 $h$ 的女朋友去中东交换。

小 $h$ 并不知道中东与北京的时差。

但是小 $h$ 得到了女朋友来回航班的起降时间。

小 $h$ 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班，给定来回程的起降时间。

假设飞机来回飞行时间相同，求飞机的飞行时间。

输入格式：

一个输入包含多组数据。

输入第一行为一个正整数 $T$，表示输入数据组数。

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下:

1. $h1:m1:s1h2:m2:s2$
2. $h1:m1:s1h3:m3:s3(+1)$
3. $h1:m1:s1h4: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\le h\le 23,0\le m,s\le 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

再一个就是本题的读入是比较烦的，如何把一个字符串中的数字信息进行摘出，有如下代码：

sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);

  

 

  
1
 

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int get_seconds(int h, int m, int s)
{
    return h * 3600 + m * 60 + s;
}

int get_time()
{
    string line;
    getline(cin, line);
    //保持一致:
    if (line.back() != ')') line += "(+0)";
    //把字符串中的数字信息读入到变量之中
    int h1, m1, s1, h2, m2, s2, d;
    sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
    
    return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
}

int main()
{
    int T;
    scanf("%d", &T);
    getchar();
    
    while (T -- )
    {
        int time = (get_time() + get_time()) / 2;
        int hours = time / 3600;
        int minutes = time % 3600 / 60;
        int seconds = time % 60;
        
        printf("%02d:%02d:%02d\n", hours, minutes, seconds);
    }
    
    return 0;
}

  

 

  
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
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

外卖店优先级

来源： 第十届蓝桥杯省赛C++A/C组,第十届蓝桥杯省赛JAVAA/B/C组

题目要求

题目描述：

“饱了么”外卖系统中维护着 $N$ 家外卖店，编号 $1$ ∼ $N$。

每家外卖店都有一个优先级，初始时 ($0$ 时刻) 优先级都为 $0$。

每经过 $1$ 个时间单位，如果外卖店没有订单，则优先级会减少 $1$，最低减到 $0$；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 $2$。

如果某家外卖店某时刻优先级大于 $5$，则会被系统加入优先缓存中；如果优先级小于等于 $3$，则会被清除出优先缓存。

给定 $T$ 时刻以内的 $M$ 条订单信息，请你计算 $T$ 时刻时有多少外卖店在优先缓存中。

输入格式：

第一行包含 $3$ 个整数 $N,M,T$。

以下 $M$ 行每行包含两个整数 $ts$ 和 $id$，表示 $ts$ 时刻编号 $id$ 的外卖店收到一个订单。

输出格式：

输出一个整数代表答案。

数据范围：

$1\le N,M,T\le 10^5,$
$1\le ts\le T,$
$1\le id\le N$

输入样例：

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出样例：

1

样例解释：

$6$ 时刻时，$1$ 号店优先级降到 $3$，被移除出优先缓存；$2$ 号店优先级升到 $6$，加入优先缓存。

所以是有 $1$ 家店 ($2$ 号) 在优先缓存中。

思路分析

首先来介绍几个数组的作用：$order$数组就是用来存储 $pair$ 信息：时刻编号和外卖店编号；$st[i]$ 是判断编号为 $i$ 的外卖店是否在有限缓存中，值为 $true$ 就是在，值为 $false$ 就是不在，$score[i]$ 用来存储编号为 $i$ 的外卖店的当前优先级，$last[i]$ 表示编号为 $i$ 的外卖店的上一次订单的时间。

我们首先对 $order$数组按照时间进行排序，然后依次去枚举每个订单，我们只需要去考虑有订单的时间点，比如编号为 $3$ 的店的订单是在 $5$ 时刻，然后下一次 $3$ 号点的订单是在 $8$ 时刻，那么对于 $3$ 号店铺而言，我们不需要去考虑 $5$ ~ $7$ 这些时刻的情况，因为肯定是没有订单的，我们只需要在处理 $8$ 时刻之前，去让店铺的优先级减去这些没有订单的时刻即可。

int j = i;
while (j < m && order[j] == order[i]) j ++;

  

 

  
1
  
2
 

因为此时的 $order$数组已经有序，上述代码的结果即 $i$ ~ $j-1$ 的范围内的值都是相同的，即对于同一家外卖店在同一时刻有多个订单，即一共订单量为：cnt = j - i;，这家点的编号为：id = order[i].y;，时刻为：tm = order[i].x;，即当前的时刻是 $tm$，现在我们要计算 $tm$ 时刻之前(从 $last[id]$ 到 $tm-1$)的信息，对应代码：

score[id] -= tm - last[id] - 1;
score[id] = max(0, score[id]);
if (score[id] <= 3) st[id] = false;

  

 

  
1
  
2
  
3
 

然后再来考虑 $tm$ 这一时刻，即我们来计算此时的优先级，以及在获得了 $j-i$ 个订单后店铺是否进入了优先缓存中，并更新 $last[id]$：

score[id] += cnt * 2;
if (score[id] > 5) st[id] = true;
last[id] = tm;

  

 

  
1
  
2
  
3
 

最后，我们要计算在每个店铺获得了最后一个订单的时刻到最终的 $t$ 时刻，需要让优先级减去多少，并计算是否让这些店铺退出优先缓存中：

for (int i = 1; i <= n; i ++ ) 
    if (last[i] < t)
    {
        score[i] -= t - last[i];
        if (score[i] <= 3) st[i] = false;
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

最终只需要遍历一遍 $st$数组计算出最终的 $res$ 即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

PII order[N];

int last[N];         // 上一次的订单时间
int score[N];        // 店铺的优先级
bool st[N];

int main()
{
    int n, m, t;
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y);
    
    sort(order, order + m);
    
    for (int i = 0; i < m;)
    {
        int j = i;
        while (j < m && order[j] == order[i]) j ++;
        int cnt = j - i, id = order[i].y, tm = order[i].x;
        
        // 当前的时刻是tm,现在我们要计算tm时刻之前(从last[id]到tm-1)的信息
        score[id] -= tm - last[id] - 1;
        score[id] = max(0, score[id]);
        if (score[id] <= 3) st[id] = false;
        
        // 现在处理t时刻的信息
        score[id] += cnt * 2;
        if (score[id] > 5) st[id] = true;
        last[id] = tm;
        
        i = j;
    }
    
    for (int i = 1; i <= n; i ++ ) 
        if (last[i] < t)
        {
            score[i] -= t - last[i];
            if (score[i] <= 3) st[i] = false;
        }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (st[i]) res ++;
        
    printf("%d\n", res);
    
    return 0;
}

  

 

  
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
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122759292