讲解七道蓝桥杯省/国赛真题（第一弹）

17153 班级活动

题目介绍

开始挑战：17153 班级活动

方法一：

#include <stdio.h>

int main()
{
    //获取数据所要使用的容器
    int id_count[100001] = { 0 };  // 用于记录每个ID出现的次数
    int total_ids = 0;  // 输入的数据总量
    int current_id = 0;  // 临时变量，用于存储当前输入的ID

    //处理数据所要使用的容器
    int count_gt2 = 0;        // 记录出现次数大于2的ID需要修改的数量
    int count_eq1 = 0;        // 记录出现次数等于1的ID的数量

    //接受答案所要使用的容器
    int total_changes = 0;    // 最终需要修改的ID总数

    // 输入数据量
    scanf("%d", &total_ids);
    // 遍历循环，并用计数器记录每个ID的数量
    for (int i = 0; i < total_ids; i++)
    {
        scanf("%d", &current_id);
        id_count[current_id]++;
    }

    // 循环判断，分别记录不同数据量的个数
    for (int n : id_count)
    {
        // 数据量为1的
        if (n == 1)
        {
            count_eq1++;
        }
        // 数据量大于2的
        else if (n >= 2)
        {
            count_gt2 += (n - 2);
        }
    }

    // 判断更改的总数
    // 若大于2的ID总数大于等于1的      
    if (count_gt2 >= count_eq1)
    {
        total_changes = count_gt2;
    }

    // 若大于2的ID总数小于等于1的
    else
    {
        total_changes = (count_eq1 - count_gt2) / 2 + count_gt2;
    }

    // 输出总数
    printf("%d", total_changes);
    return 0;
}

精彩代码模块

将学生的ID号存起来并记录各个ID号人的数量

// 输入数据量
scanf("%d", &total_ids);
// 遍历循环，并用计数器记录每个ID的数量
for (i = 0; i < total_ids; i++)
{
    scanf("%d", &current_id);
    id_count[current_id]++;
}

解题思路分析

想要解决这道题我们要能够想到：偶数个学生的ID号会有哪些情况，而这些情况下又有什么规律。

这道题的突破口就是：我们发现 老师要修改的次数 和 出现次数等于1的ID与出现次数大于2的ID需要修改的数量 有关。

例如：

所以：total_changes 的计算基于以下两个变量：

• count_eq1：出现次数等于1的ID数量。
• count_gt2：出现次数大于2的ID需要修改的数量（即： n - 2，其中 n 是ID出现的次数）

---

1. 如果 count_gt2 >= count_eq1：

   • 表示出现次数大于2的ID数量较多，可以直接用 count_gt2 作为需要修改的总数。

     total_changes = count_gt2
     

2. 如果 count_gt2 < count_eq1：

   • 表示出现次数等于1的ID数量较多，需要将多余的 count_eq1 - count_gt2 个ID两两配对修改。因此需要修改的数量为 (count_eq1 - count_gt2) / 2

   • 最终需要修改的总数为：

     total_changes = (count_eq1 - count_gt2) / 2 + count_gt2
     

19718 回文字符串

开始挑战：19718 回文字符串

题目介绍

方法一：

#include <iostream>
#include <vector>
using namespace std;

// 此函数用于判断输入的字符串是否满足特定条件
bool isStringValid() 
{
    vector<int> validIndices;  // 存储字符串中非 'l'、'q'、'b' 字符的索引
    string inputString;
    cin >> inputString;

    int stringLength = inputString.size();
    // 遍历字符串，将非 'l'、'q'、'b' 字符的索引存入 validIndices 向量
    for (int i = 0; i < stringLength; i++) 
    {
        if (inputString[i] != 'l' && inputString[i] != 'q' && inputString[i] != 'b') 
        {
            validIndices.push_back(i);
        }
    }

    // 如果没有非 'l'、'q'、'b' 字符，认为字符串有效 ---->意思是说：输入的字符串是只有 'l'、'q'、'b' 组成的，即它一定可以转换为回文串
    if (validIndices.size() == 0) 
    {
        return true;
    }


    //现在剩下的字符串的特征：
    //1.含有'l'、'q'、'b' 字符但不全是    
    //2.不含有'l'、'q'、'b' 字符

    // 非 'l'、'q'、'b' 字符的最左索引
    int leftMostIndex = validIndices[0];
    // 非 'l'、'q'、'b' 字符的最右索引
    int rightMostIndex = validIndices[validIndices.size() - 1];
    // 用于向内扩散检查的左索引
    int leftin = leftMostIndex;
    // 用于向内扩散检查的右索引
    int rightin = rightMostIndex;
    // 用于向外扩散检查的左索引
    int leftOut = leftMostIndex;
    // 用于向外扩散检查的右索引
    int rightOut = rightMostIndex;

    // 向内扩散检查，直到左右索引相遇或交叉
    while (leftin <= rightin && inputString[leftin] == inputString[rightin])
    {
        leftin++;
        rightin--;
    }
    //如果该字符串通过了向内扩散检查说明：该字符除了 'l'、'q'、'b' 字符的组成部分以外的字符是回文的
    //现在就是还不知道'l'、'q'、'b' 字符的组成部分是否可以可转换为回文串

    // 向外扩散检查，直到左索引越界
    while (leftOut >= 0 && rightOut < stringLength && inputString[leftOut] == inputString[rightOut]) 
    {
        leftOut--;
        rightOut++;
    }

    // 只有当向内扩散检查通过且向外扩散检查左索引越界时，字符串才有效
    return leftin > rightin && leftOut < 0;
    //leftin > rightin   说明该字符串是由：内部是回文的才跳出了while循环->符合要求
    //leftOut < 0        说明该字符串是由：左索引越界才跳出了while循环->符合要求
}

int main() 
{
    int testCases;
    cin >> testCases;

    // 循环处理每个测试用例
    while (testCases--) 
    {
        if (isStringValid()) 
        {
            cout << "Yes" << endl;
        }
        else 
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

代码执行过程

精彩代码模块

差别化存储字符串中字符的下标

//差别化存储字符串中字符的下标
vector<int> validIndices;
string inputString;
cin >> inputString;

for (int i = 0; i < inputString.size(); i++)
{
    if (inputString[i] != 'l' && inputString[i] != 'q' && inputString[i] != 'b')
    {
        validIndices.push_back(i);
    }
}

解题思路分析

想要解决这道题我们还是要分析目标对象有哪些特征：即，哪些字符串可以满足题目的要求？

或者说满足要求的字符串都有哪些特征？

---

所以说我们要对于用户输入的每个字符串可能出现的所有情况进行分类：

1. 字符串本身全部由 ‘l’、‘q’、‘b’ 组成 —> 字符串一定是回文串
2. 字符串本身部分由 ‘l’、‘q’、‘b’ 组成
   • 字符串本身就是回文串 —> 字符串是回文串
   • 字符串本身不是回文串，但是可以转换为回文串 —> 字符串是回文串
   • 字符串本身不是回文串，也不可以转换为回文串 —> 字符串不是回文串
3. 字符串本身不含有 ‘l’、‘q’、‘b’ 组成
   • 字符串本身就是回文串 —> 字符串是回文串
   • 字符串本身就不是回文串 —> 字符串不是回文串

---

因此，我们可以通过用户输入的字符串的所用可能分析出我们程序的大致流程：

1. 挑出：本身全部由 ‘l’、‘q’、‘b’ 组成的字符串。 （挑出）
2. 剔除：
   • 本身部分由 ‘l’、‘q’、‘b’ 组成的字符串中的：
     • 字符串本身不是回文串，也不可以转换为回文串 （剔除）
   • 本身不含有 ‘l’、‘q’、‘b’ 组成的字符串中的：
     • 字符串本身就不是回文串 （剔除）

很直观的我们可以看出剔除中第1中情况是最困难的。

因为你不能简单的通过判断一个字符串是否是回文串来直接剔除，这是因为这类字符串中有一种情况是：字符串本身不是回文串，但是可以转换为回文串

我们先观察几个这类字符串的样例:

bbbgmgbbb   yes	字符串本身就是回文串
bbbgmbbb	no  字符串本身不是回文串，也不可以转换为回文串
bbbgmgbbbq	yes	字符串本身不是回文串，但是可以转换为回文串
qbbbgmgbbb	no  字符串本身不是回文串，也不可以转换为回文串

所以：剔除剔除中的第1中情况的任务就具象为了

bbbgmgbbbq	yes	//同过两次while循环的检查（保留）
bbbgmbbb	no  //使用：向内扩散检查（剔除）
qbbbgmgbbb	no  //使用：向外扩散检查（剔除）

1216 走迷宫

题目介绍

开始挑战：1216 走迷宫

方法一：

#include <iostream>
#include <queue>
using namespace std;


int main()
{
    // 定义迷宫地图和访问标记数组
    int maze[100][100];    // 迷宫地图，1表示通路，0表示障碍物
    int visited[100][100] = { 0 };  // 访问标记数组，1表示已访问，0表示未访问

    int rows, cols;          // 迷宫的行数和列数
    cin >> rows >> cols;     // 输入迷宫的行数和列数

    // 输入迷宫地图
    for (int i = 1; i <= rows; i++)
    {
        for (int j = 1; j <= cols; j++)
        {
            cin >> maze[i][j]; // 输入每个格子的状态（1表示通路，0表示障碍物）
        }
    }

    int startRow, startCol;  // 起点坐标
    int endRow, endCol;      // 终点坐标
    // 输入起点和终点坐标
    cin >> startRow >> startCol >> endRow >> endCol;

    // 定义点的结构体，表示迷宫中的一个位置
    struct Position
    {
        int row, col;    // 点的行和列坐标
        int steps;       // 从起点到该点的步数
    };//记得加;号
    queue<Position> explorationQueue; // 申请队列，用于BFS遍历

    // 初始化起点
    Position start;
    start.row = startRow;    // 起点的行坐标
    start.col = startCol;    // 起点的列坐标
    start.steps = 0;         // 起点到起点的步数为0

    explorationQueue.push(start);      // 将起点入队
    visited[startRow][startCol] = 1;   // 标记起点为已访问

    int found = 0;    // 标记是否找到终点

    // 定义四个移动方向：右、下、左、上
    int rowDirection[4] = { 0, 1, 0, -1 };
    int colDirection[4] = { 1, 0, -1, 0 };

    // BFS核心逻辑
    while (!explorationQueue.empty())//容器为空时empty这函数返回真--->容器为空时不进入while循环
    {
        int currentRow = explorationQueue.front().row; // 获取队首元素的行坐标
        int currentCol = explorationQueue.front().col; // 获取队首元素的列坐标

        // 如果当前点是终点，输出步数并结束
        if (currentRow == endRow && currentCol == endCol)
        {
            found = 1; // 标记已找到终点
            cout << explorationQueue.front().steps; // 输出最短步数
            break;
        }

        // 尝试向四个方向移动
        for (int k = 0; k < 4; k++)
        {
            int newRow = explorationQueue.front().row + rowDirection[k]; // 计算新位置的行坐标
            int newCol = explorationQueue.front().col + colDirection[k]; // 计算新位置的列坐标

            // 如果新位置是通路且未被访问过
            if (maze[newRow][newCol] == 1 && visited[newRow][newCol] == 0)
            {
                Position nextPosition;
                nextPosition.row = newRow;                     // 新位置的行坐标
                nextPosition.col = newCol;                     // 新位置的列坐标
                nextPosition.steps = explorationQueue.front().steps + 1;   // 步数加1

                explorationQueue.push(nextPosition);                    // 将新位置入队
                visited[newRow][newCol] = 1;                  // 标记新位置为已访问
            }
        }

        explorationQueue.pop(); // 拓展完当前点后，将其出队
    }

    // 如果未找到终点，输出-1
    if (found == 0)
    {
        cout << "-1";
    }

    return 0;
}

代码执行过程

19709 好数

题目介绍

开始挑战：19709 好数

方法一：

#include <stdio.h>

int main() 
{
    int inputNumber, count = 0; // inputNumber 是输入的整数，count 用于计数符合条件的数
    scanf("%d", &inputNumber);

    // 从 inputNumber 开始递减到 1
    for (; inputNumber > 0; inputNumber--) 
    {
        int currentNumber = inputNumber; // currentNumber 是当前正在检查的数

        // 检查 currentNumber 是否满足条件
        while (currentNumber > 0) 
        {
            // 如果 currentNumber 的最后一位是奇数，去掉最后一位
            if (currentNumber % 2 != 0) 
            {
                currentNumber /= 10;
            }
            else 
            {
                break; // 如果遇到偶数，跳出循环
            }

            // 如果 currentNumber 的最后一位是偶数，去掉最后一位
            if (currentNumber % 2 == 0) 
            {
                currentNumber /= 10;
            }
            else 
            {
                break; // 如果遇到奇数，跳出循环
            }
        }

        // 如果 currentNumber 变为 0，说明满足条件，count 加 1
        if (currentNumber == 0)// 排除currentNumber是被break出来的，其值并不等于0的情况
        {
            count++;
        }
    }

    // 输出符合条件的数的个数
    printf("%d", count);
    return 0;
}

解题思路分析

核心：我们要看出其中的循环情景

即是：

1. 第一步：奇数位是否为奇数
2. 第二步：偶数位是否为偶数
3. 第三步：奇数位是否为奇数
4. 第四步：偶数位是否为偶数
5. 第N步：…

所以：这道题要分为双重循环，其中内层循环主要就是不断的判断以下的两步：

• 奇数位是否为奇数
• 偶数位是否为偶数

持续循环的动力：

满足奇数位是奇数、偶数位是偶数时，就使用currentNumber /= 10 不断的改变数字。

跳出循环的条件：

• 成功：数字最终变为0时—>意味着这个数字通过了每位的判断

• 失败：数字未通过了每位的判断，通过break跳出了循环

方法二：

#include <stdio.h>
#include <stdbool.h>

// 函数：检查一个数字是否是“好数”
bool isGoodNumber(int number) 
{
    int currentPosition = 1; // 当前位数，从个位开始（奇数位）

    while (number > 0) 
    {
        int currentDigit = number % 10; // 获取当前位的数字

        // 检查当前位的数字是否符合“好数”的定义
        if ((currentPosition % 2 == 1 && currentDigit % 2 == 0) || // 奇数位应为偶数
            (currentPosition % 2 == 0 && currentDigit % 2 != 0)) // 偶数位应为奇数
        { 
            return false; // 不符合条件，返回 false
        }

        number /= 10; // 去掉当前位的数字
        currentPosition++; // 移动到下一个位置
    }

    return true; // 所有位都符合条件，返回 true
}

int main() 
{
    int maxNumber; // 用户输入的最大数字
    scanf("%d", &maxNumber);

    int count = 0; // 统计“好数”的个数

    // 遍历从 1 到 maxNumber 的所有数字
    for (int currentNumber = 1; currentNumber <= maxNumber; currentNumber++) 
    {
        if (isGoodNumber(currentNumber)) 
        {
            count++; // 如果是“好数”，计数器加 1
        }
    }

    // 输出“好数”的个数
    printf("%d\n", count);
    return 0;
}

精彩代码模块

不断的获取一个数字的每一位

//不断的获取一个数字的每一位
while (number > 0)
{
    int currentDigit = number % 10; // 获取当前位的数字
    number /= 10; // 去掉当前位的数字
}

19712 数字接龙

题目介绍

开始挑战：19712 数字接龙

方法一：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int gridSize; // 网格大小
int modValue; // 模数 k

// 网格和访问标记
vector<vector<int>> grid(12, vector<int>(12, -1));         // 网格值
vector<vector<bool>> visited(12, vector<bool>(12, false)); // 访问标记

// 八个方向的移动增量：上、右上、右、右下、下、左下、左、左上（顺时针）
int directionX[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int directionY[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };


// 边标记，用于防止对角线交叉
bool edgeMark[12][12][12][12]; // edgeMark[x][y][i][j] 表示有一条从 (x,y) -> (i,j) 的边

// 深度优先搜索函数
bool depthFirstSearch(int x, int y, string path, int step)
{
    // 如果到达终点且步数等于网格大小，输出路径并返回
    if (step == gridSize * gridSize && x == gridSize && y == gridSize)
    {
        cout << path << endl;
        return true;
    }

    // 遍历八个方向
    for (int i = 0; i < 8; i++)
    {
        int nextX = x + directionX[i];
        int nextY = y + directionY[i];

        //1.进行第一次的排除：（常规）---->保证新位置之前没有访问过
        // 如果下一个位置已被访问，跳过
        if (visited[nextX][nextY])
        {
            continue;
        }
        //2.进行第二次的排除：（跟题目的要求）--->保证新位置不会形成对角线交叉
        // 检查是否形成对角线交叉
        if (edgeMark[x][nextY][nextX][y] || edgeMark[nextX][y][x][nextY])
        {
            continue;
        }

        //3.经过两次排除后，如果可进入的到if循环的话说明该新位置可以作为下一个去的地方
        // 检查下一个位置的值是否符合条件--->保证新位置是数字接龙
        if (grid[nextX][nextY] == (grid[x][y] + 1) % modValue)
        {
            // 标记边和访问状态
            edgeMark[x][y][nextX][nextY] = true;
            visited[nextX][nextY] = true;

            // 递归搜索
            if (depthFirstSearch(nextX, nextY, path + (char)('0' + i), step + 1))
            {
                return true;
            }  

            // 回溯：取消标记
            visited[nextX][nextY] = false;
            edgeMark[x][y][nextX][nextY] = false;
        }
    }
    //八方向尝试都没能进入递归的话----> 进入回溯的阶段
    return false;
}

int main01()
{
    // 输入网格大小和模数
    cin >> gridSize >> modValue;

    // 输入网格值并初始化访问标记
    for (int i = 1; i <= gridSize; i++)
    {
        for (int j = 1; j <= gridSize; j++)
        {
            cin >> grid[i][j];
            visited[i][j] = false;
        }
    }

    // 标记起点为已访问
    visited[1][1] = true;

    // 开始深度优先搜索
    if (!depthFirstSearch(1, 1, "", 1))
    {
        cout << -1 << endl; // 如果没有找到路径，输出 -1
    }
        
    return 0;
}

代码执行过程

代码片段讲解

片段一：

// 网格和访问标记
vector<vector<int>> grid(12, vector<int>(12, -1));         // 网格的值
vector<vector<bool>> visited(12, vector<bool>(12, false)); // 访问标记

这两行代码定义了两个 二维的动态数组（vector），分别用于存储 网格的值 和 访问标记

---

1. grid：网格值

vector<vector<int>> grid(12, vector<int>(12, -1));

含义：

• 定义了一个 12 x 12 的二维动态数组 grid，用于存储网格的值。
• 每个元素的初始值为 -1

解释：

vector<vector<int>> grid：是一个二维的动态数组，外层 vector 存储行，内层 vector 存储列。

• 外层 vector 的大小为 12，表示有 12 行
• 内层 vector<int>(12, -1) 表示每行有 12 列，且每个元素的初始值为 -1

---

2. visited：访问标记

vector<vector<bool>> visited(12, vector<bool>(12, false));

含义：

• 定义了一个 12 x 12 的二维动态数组 visited，用于标记网格中的位置是否已被访问。
• 每个元素的初始值为 false

解释：

vector<vector<bool>> visited：是一个二维的动态数组，外层 vector 存储行，内层 vector 存储列。

• 外层 vector 的大小为 12，表示有 12 行
• 内层 vector<bool>(12, false) 表示每行有 12 列，且每个元素的初始值为 false

疑问：为什么使用 vector？

1. 动态大小：vector 是 C++ 中的动态数组，可以根据需要调整大小。
   • 虽然这里固定为 12 x 12，但使用 vector 可以方便地扩展到更大的网格
2. 方便初始化：vector 支持在定义时初始化所有元素。
   • 例如： vector<int>(12, -1) 将所有元素初始化为 -1
3. 易于操作vector 提供了丰富的成员函数。
   • 如：push_back、size 等，方便操作数据

片段二：

// 边标记，用于防止对角线交叉
bool edgeMark[12][12][12][12]; // edgeMark[x][y][i][j] 表示有一条从 (x,y) -> (i,j) 的边

// 检查是否形成对角线交叉
if (edgeMark[x][nextY][nextX][y] || edgeMark[nextX][y][x][nextY])
{
    continue;
}

这段代码通过 edgeMark 数组检查是否在移动过程中形成了对角线交叉，以此来 防止路径形成对角线交叉

对角线交叉：在网格中，对角线交叉是指两条路径在对角线上交叉。

• 从 (x, y) 移动到 (nextX, nextY)
• 从 (x, nextY) 移动到 (nextX, y)

如果这两条路径同时存在，就会形成对角线交叉。

---

解释：edgeMark[x1][y1][x2][y2] 表示从 (x1, y1) 到 (x2, y2) 的边是否被标记。

edgeMark[x][nextY][nextX][y] || edgeMark[nextX][y][x][nextY]

• 检查是否存在从 (x, nextY) 到 (nextX, y) 的边，或者从 (nextX, y) 到 (x, nextY) 的边。
• 如果存在，说明形成了对角线交叉，跳过当前移动。

---

示例：

假设当前移动是从 (1, 1) 到 (2, 2)：

• 检查是否存在从 (1, 2) 到 (2, 1) 的边，或者从 (2, 1) 到 (1, 2) 的边。
• 如果存在，说明形成了对角线交叉，跳过当前移动。

片段三：

path + (char)('0' + i)

这一表达式是C++ 里用于字符串拼接操作。

---

分析：

1.'0' + i

• 在 C++ 中，字符类型（char）本质上是以整数形式存储的，每个字符对应着一个 ASCII 码值，字符 '0' 的 ASCII 码值是 48

  所以：当你将 '0' 与一个整数 i 相加时，实际上是在 '0' 的 ASCII 码值基础上加上 i

  • 例如：若 i 为 1，'0' + 1 的结果就是 49，而 ASCII 码值 49 对应的字符是 '1'

2.(char)('0' + i)

• 由于 '0' + i 的结果是一个整数，为了将其转换为字符类型，使用了强制类型转换 (char)，这样就把计算得到的整数转换为对应的字符

3.path + (char)('0' + i)

• path 是一个字符串类型（ std::string）的变量，+ 运算符在 std::string 类中被重载，用于实现字符串拼接操作
• 所以 path + (char)('0' + i) 的作用是把 path 字符串和字符 (char)('0' + i) 拼接在一起，生成一个新的字符串。

精彩代码模块

将一个数字拼接到字符串里面

//将一个数字拼接到字符串里面
path + (char)('0' + i) 

解题思路分析

对于深度搜索的该怎么搜？

在整个for循环里：

1. 找一个新位置
2. 判断新位置是否符合要求
   • 保证新位置之前没有访问过
   • 保证新位置不会形成对角线交叉
   • 保证新位置是数字接龙
3. 记录新位置
   • 记录新位置的访问
   • 记录新位置的路线
4. 递归寻找下一个新位置

判断：若是在八个方向上都没能找到新位置，则进入回溯阶段：

1. 抹去新位置
   • 取消记录新位置的访问
   • 取消记录新位置的路线

1025 答疑

题目介绍

开始挑战：1025 答疑

方法一：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 自定义比较函数，用于排序
bool compareTasks(const vector<long long>& taskA, const vector<long long>& taskB)
{
    return taskA[0] + taskA[1] < taskB[0] + taskB[1];
}
//如果 taskA 的总时间小于 taskB 的总时间，则返回 true，表示 taskA 应该排在 taskB 前面
//否则，返回 false，表示 taskB 应该排在 taskA 前面。

int main() 
{
    int taskCount;
    cin >> taskCount;

    // 定义一个二维数组来存储每个任务的信息
    vector<vector<long long>> tasks(taskCount, vector<long long>(2));

    // 输入每个任务的信息
    for (int i = 0; i < taskCount; i++) 
    {
        long long preparationTime, executionTime, cleanupTime;
        cin >> preparationTime >> executionTime >> cleanupTime;

        tasks[i][0] = preparationTime + executionTime; // 任务的总准备和执行时间
        tasks[i][1] = cleanupTime;                     // 任务的清理时间
    }

    // 按照自定义的比较函数对任务进行排序
    sort(tasks.begin(), tasks.end(), compareTasks);

    long long currentTime = 0; // 当前时间
    long long totalCost = 0;   // 总成本

    // 计算总成本
    for (int i = 0; i < taskCount; i++) 
    {
        //更新当前时间
        currentTime += tasks[i][0]; // 累加任务的准备和执行时间
        
        //该学生要发消息了，将他的时间累加到总时间中
        totalCost += currentTime;   // 累加当前时间到总成本

        //更新当前时间
        currentTime += tasks[i][1]; // 累加任务的清理时间
    }

    // 输出总成本
    cout << totalCost << endl;
    return 0;
}

代码片段讲解

片段一：

// 自定义比较函数，用于排序
bool compareTasks(const vector<long long>& taskA, const vector<long long>& taskB)
{
    return taskA[0] + taskA[1] < taskB[0] + taskB[1];
}

//处理数据：为提问的学生规划最佳的提问顺序
sort(tasks.begin(), tasks.end(), mysort);//对二维数组中的元素进行排序

这段代码的核心功能是对任务列表进行排序，排序的规则由自定义的比较函数 compareTasks 定义。

---

1.自定义比较函数 compareTasks

compareTasks()：用于比较两个任务的总时间（taskA[0] + taskA[1] 和 taskB[0] + taskB[1]）

• 它的返回值决定了 taskA 和 taskB 在排序后的顺序

  • 如果 taskA 的总时间小于 taskB 的总时间，返回 true，表示 taskA 应该排在 taskB 前面
  • 如果 taskA 的总时间大于或等于 taskB 的总时间，返回 false，表示 taskB 应该排在 taskA 前面

---

2.排序函数 sort

sort()：使用自定义的比较函数 compareTasks 对任务列表 tasks 进行排序。

• 排序的规则是按照任务的总时间（task[0] + task[1]）升序排序。

参数：

• tasks.begin()：指向 tasks 容器的第一个元素的迭代器，表示排序的起始位置。
• tasks.end()：指向 tasks 容器的最后一个元素之后位置的迭代器，表示排序的结束位置（不包含该位置的元素）。
• compareTasks：自定义的比较函数，用于确定排序的规则。sort 函数会根据这个比较函数来比较元素之间的大小关系，从而对元素进行排序。

为什么需要自定义排序规则？

默认情况下，sort 函数会对任务列表按照字典序（即：逐个元素比较）进行排序。但在某些情况下，我们需要根据特定的规则进行排序。

• 例如：在这个问题中，我们需要按照任务的总时间（task[0] + task[1]）进行排序，而不是默认的字典序。

示例：运行的示例

假设输入为：

3
2 3 1
4 2 2
1 5 3

• 任务列表：

  [
    {5, 1}, // 任务1：总时间为 5 + 1 = 6
    {6, 2}, // 任务2：总时间为 6 + 2 = 8
    {6, 3}  // 任务3：总时间为 6 + 3 = 9
  ]
  

• 排序后的任务列表：

  [
    {5, 1}, // 任务1
    {6, 2}, // 任务2
    {6, 3}  // 任务3
  ]
  

精彩代码模块

将一个3*2的二维数组中的每一行作为一个元素进行自定义排序

// 自定义比较函数，用于排序
bool compareTasks(const vector<long long>& taskA, const vector<long long>& taskB)
{
    return taskA[0] + taskA[1] < taskB[0] + taskB[1];
}

// 定义一个二维数组来存储每个任务的信息
vector<vector<long long>> tasks(taskCount, vector<long long>(2));

//处理数据：为提问的学生规划最佳的提问顺序
sort(tasks.begin(), tasks.end(), mysort);//对二维数组中的元素进行排序

使用一重for循环对二维数组进行赋值

// 定义一个二维数组来存储每个任务的信息
vector<vector<long long>> tasks(taskCount, vector<long long>(2));

// 输入每个任务的信息
for (int i = 0; i < taskCount; i++)
{
    long long preparationTime, executionTime, cleanupTime;
    cin >> preparationTime >> executionTime >> cleanupTime;

    tasks[i][0] = preparationTime + executionTime; // 任务的总准备和执行时间
    tasks[i][1] = cleanupTime;                     // 任务的清理时间
}

在不断变化的时间里不断累加特定时刻的值

long long currtime = 0;//记录当前的时间
long long sumtime = 0;//统计所有时间发消息的时刻，并相加

//处理数据：累加得到最后一名同学发消息的时间
for (int i = 0; i < student; i++)
{
    //更新当前时间
    currtime += tasks[i][0];

    //该学生要发消息了，将他的时间记下
    sumtime += currtime;

    //更新当前的时间
    currtime += tasks[i][1];

}

cout << sumtime << endl;

解题思路分析

这道题的问题说的挺复杂的，其实简单点说就是：

输出同学们在课程群里面发消息的时刻之和最小值 完全等价于以下两点：

1. 将这数量小于1000个的学生的提问顺序安排为：花时间少的先提问，花时间多的后提问

2. 然后按这个提问顺序累加出所有学生发消息的时刻

---

解题的独特思想：

按理来说存储每位学生的二维数组应该准备3列：1.准备时间 2.答疑时间 3.清理时间

但是本题我们要统计的学生发消息时间是在2和3之间，所以不如将1与2合并为一个时间。
但是题目的输入规则要求是对于每位同学都要输入3个元素 —> 所以这里的为二维数组赋值的方法与之前的有所不同。

19723 分布式队列

题目介绍

开始挑战：19723 分布式队列

方法一：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() 
{
    int nodeCount;
    cin >> nodeCount;

    // 使用一个二维数组来表示主节点和副节点的队列
    vector<vector<int>> nodes(nodeCount);//由于时无线列，所以这里定义好列，只是定义好行

    string command;
    while (cin >> command) // 读取命令直到无法读取为止
    { 
        int nodeIndex;

        // 如果是添加命令，将数据添加到主节点
        if (command == "add")
        {
            cin >> nodeIndex;
            nodes[0].push_back(nodeIndex);
        }

        // 如果是同步命令，将主节点的数据同步到指定的副节点
        else if (command == "sync") 
        {
            cin >> nodeIndex;
            if (nodes[nodeIndex].size() < nodes[0].size()) 
            {
                nodes[nodeIndex].push_back(nodes[0][nodes[nodeIndex].size()]);
            }
        }

        // 如果是查询命令，找到同步最少的副节点的同步数量
        else 
        {
            int minSyncCount = 1e9;
            for (int i = 1; i < nodeCount; i++) 
            {
                minSyncCount = min((int)nodes[i].size(), minSyncCount);
            }
            cout << minSyncCount << endl;
        }
    }

    return 0;
}

代码片段解释

片段一：

int minSyncCount = 1e5;

• int：是 C++ 中常用的整数类型，在大多数系统上，它通常占用 4 个字节。

  • 可表示的数值范围大约是 -2147483648 到 2147483647

• 1e5：是一种科学计数法的表示方式。

  • 在 C++ 里，它等同于 100000（也就是 10 的 5 次方）

之所以这样写是因为，题目要求主队里中添加的element的取值范围为： (0 \leq element \leq 10^{5})

片段二：

min((int)nodes[i].size(), minSyncCount);

为什么需要强制类型转换？

min()：要求其两个参数的类型相同或者能够进行隐式类型转换，如果两个参数的类型不一致，编译器会报错。

问题：

• nodes[i].size() 返回 size_t 类型。
  • 在大多数系统中，size_t 是 unsigned long 或 unsigned long long 的别名
• minSyncCount 是 int 类型。
• size_t 和 int 是两种不同的类型，无法直接进行比较。

解决方法：

• 将 nodes[i].size() 强制转换为 int 类型，使其与 minSyncCount 的类型一致。

精彩代码模块

根据输入的字符串的不同进行不同的操作

int nodeIndex;
string command;
while (cin >> command) // 读取命令直到无法读取为止
{  
    // 如果是添加命令，将数据添加到主节点
    if (command == "add")
    {
       
    }

    // 如果是同步命令，将主节点的数据同步到指定的副节点
    else if (command == "sync") 
    {
      
    }

    // 如果是查询命令，找到同步最少的副节点的同步数量
    else 
    {
        
    }
}

为二维数组中某行添加其他行该列的元素

cin >> nodeIndex;
if (nodes[nodeIndex].size() < nodes[0].size())
{
    nodes[nodeIndex].push_back(nodes[0][nodes[nodeIndex].size()]);
}

解题思路分析

这道有一些比较复杂的名词：

元素的可见性：只有当主节点中的某个元素被同步到了所有副节点时，这个元素才具有可见性。

举例说明：假设存在一个主节点和两个副节点。

• 主节点队列依次添加元素 1、2、3 ，一开始，这三个元素都不可见。

• 当对第一个副节点执行三次 sync 操作，它同步了 1、2、3 ，但第二个副节点还未同步，此时这三个元素依然不可见。

• 只有当第二个副节点也通过多次 sync 操作，将 1、2、3 都同步后，元素 1、2、3 才都具有可见性 。

---

这道题的难点主要是：

同步操作：

1. 需不需要同步 ?—> 副队列中缺不缺元素 —> 副队列中的元素数量小于主队列的元素的数量 —> 证明副队列缺元素
2. 怎么同步缺少的元素?

查询操作：

1. 怎么去判断可见性为多少? —> 所有副队列中元素数量最少的队列中的元素的数量就是整个队列中的元素的可见性