C++
B3951 [GESP样题五级] 小杨的队列
admin SU @ 2025-5-22 21:59:17

B3951 [GESP样题五级] 小杨的队列

题目描述

小杨的班级里共有 $N$ 名同学，学号从 $0$ 至 $N-1$ 。某节课上，老师要求同学们进行列队。具体来说，老师会依次点名 $M$ 名同学，让他们加入队伍。每名新入队的同学需要先站到队伍末尾（刚开始队伍里一个人都没有，所以第一个入队的同学只需要站好即可），随后，整个队伍中的所有同学需要按身高从低到高重新排序（身高相同的同学之间的顺序任意）。

排队很容易，但重新排序难倒了同学们。稍加讨论后，他们发现可以通过交换位置的方法来实现排序。具体来说，他们可以让队伍中的两名同学交换位置这样整个队伍的顺序就会发生变化，多经过这样的几次交换后，队伍的顺序就可以排好。

例如：队伍中有 $4$ 名同学，学号依次为 $10,17,3,25$ ，我们可以令 $3$ 号同学和 $10$ 号同学交换位置，则交换后的队伍顺序变为 $3,17,10,25$ ，这就是一次交换位置。

聪明的小杨想要知道：在老师每次点名一位新同学加入队伍后，在原有队伍的基础上，同学们最少要进行几次交换位置，才能完成老师按身高排序的要求。

输入格式

第一行一个整数 $N$ ，表示同学的数量
第二行 $N$ 个用空格隔开的正整数，依次表示学号为 $0,1,$ … $,N-1$ 的同学的身高（不超过 $2,147,483,647$ ）。
第三行一个整数 $M$ ，表示老师点名的数量。
接下来 $M$ 行，依次描述 $M$ 次点名：每行一个整数 $x$ （ $0 \le x<N$ ），表示要求学号为 $x$ 的同学加入队伍。保证该名同学此前不在队伍中。

输出格式

输出 $M$ 行，依次表示对于每次点名，同学们最少要进行几次交换位置，才能完成按身高排序的要求。

输入输出样例 #1

输入 #1

5
170 165 168 160 175
4
0
3
2
1

输出 #1

输入输出样例 #2

输入 #2

4
20 20 20 10
4
0
1
2
3

输出 #2

说明/提示

对于所有的测试点，保证 $1 \le M \le N \le 2000$ 。对于 $50\%$ 的测试点，保证所有同学的身高互不相同。

admin SU @ 2025-5-22 22:13:46

🏫 B3951 [GESP样题五级] 小杨的队列教程

🎯 一、题目描述

小杨的班级里共有 $N$ 名同学，学号从 $0$ 至 $N-1$ 。某节课上，老师要求同学们按身高排序进行列队。每次点名一位同学加入队伍后，整个队伍需要重新排序（身高相同的同学之间的顺序任意）。聪明的小杨想知道：在老师每次点名一位新同学加入队伍后，在原有队伍的基础上，最少要进行几次交换位置，才能完成按身高排序的要求。

📊 二、核心知识点与算法

🔍 1. 插入排序

属性	内容
定义	每次将一个新元素插入到已排序部分的正确位置
应用场景	每次点名一位同学后，更新队列并计算最少交换次数

🔹 原理图：

初始队列: [170]
加入 160 -> [170, 160] (需交换一次)
最终队列: [160, 170]

📈 2. 动态数组 Vector

属性	内容
使用场景	动态维护当前队列
优势	支持随机访问和动态调整大小

⏰ 3. 时间复杂度分析

类型	复杂度	解释
时间复杂度	$O(M^2)$	每次插入操作的时间复杂度为 $O(k)$ ，总共有 $M$ 次插入操作
空间复杂度	$O(N + M)$	存储队列的空间为 $O(M)$ ，存储初始身高数组的空间为 $O(N)$

💻 三、代码实现

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

int main() {
    int N;
    cin >> N;
    vector<int> a(N); // 同学的身高数组
    
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    int M;
    cin >> M;
    vector<int> b; // 当前队列

    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        b.push_back(a[x]); // 插入新同学到队尾

        int cnt = 0; // 交换次数
        int len = b.size();

        // 从前往后扫描，将比当前元素大的元素交换到后面
        for (int j = 0; j < len - 1; ++j) {
            if (b[j] > b[len - 1]) {
                swap(b[j], b[len - 1]);
                ++cnt;
            }
        }

        cout << cnt << endl;
    }

    return 0;
}

🧩 四、代码详解

✅ 输入处理

读取数据：
- 读取同学数量 N 和每个同学的身高数组 a。
- 读取老师点名次数 M 和每次点名的学号 x。

cin >> N;
vector<int> a(N);
for (int i = 0; i < N; ++i) {
    cin >> a[i];
}

int M;
cin >> M;
vector<int> b; // 当前队列

✅ 队列维护

动态添加新同学：
- 使用 push_back() 方法将新同学的身高添加到队列末尾。

b.push_back(a[x]); // 插入新同学到队尾

✅ 排序与交换

模拟插入排序：
- 从队列起始位置开始，将比新同学高的同学与其交换，直到新同学到达正确的位置。
- 记录交换次数 cnt。

int cnt = 0; // 交换次数
int len = b.size();
for (int j = 0; j < len - 1; ++j) {
    if (b[j] > b[len - 1]) {
        swap(b[j], b[len - 1]);
        ++cnt;
    }
}
cout << cnt << endl;

📝 五、示例解析

📌 样例 1

输入：
5
170 165 168 160 175
4
0
3
2
1
输出：
0
1
1
2

🧠 解析：

插入 0 号同学（170）：队列 [170]，无需交换。
插入 3 号同学（160）：队列 [170, 160]，交换 170 和 160，交换次数为 1。
插入 2 号同学（168）：队列 [160, 170, 168]，交换 170 和 168，交换次数为 1。
插入 1 号同学（165）：队列 [160, 168, 170, 165]，交换 168 和 165，再交换 170 和 165，交换次数为 2。

📌 样例 2

输入：
4
20 20 20 10
4
0
1
2
3
输出：
0
0
0
1

🧠 解析：

插入 0 号同学（20）：队列 [20]，无需交换。
插入 1 号同学（20）：队列 [20, 20]，无需交换。
插入 2 号同学（20）：队列 [20, 20, 20]，无需交换。
插入 3 号同学（10）：队列 [20, 20, 20, 10]，交换 20 和 10，交换次数为 1。

⚠️ 六、常见问题与注意事项

🔁 交换次数的数学意义

最少交换次数等于新同学前面比它高的同学的数量。
- 例如，队列 [170, 160] 插入 168 后，需要交换一次（170 与 168 交换）。

🔄 优化方向

如果仅需计算交换次数而不实际移动元素，可以通过二分查找确定新同学在有序队列中的插入位置。但本题要求输出交换次数，因此仍需模拟交换过程。

🎨 七、附加资源（图表+工具）

📊 图表说明

队列状态	交换次数	解析
[170]	0	初始队列，无需交换
[170, 160]	1	交换 170 和 160
[160, 170, 168]	1	交换 170 和 168
[160, 168, 170, 165]	2	先交换 168 和 165，再交换 170 和 165

🛠️ 工具推荐

工具名称	功能
WolframAlpha	在线计算与可视化
Visual Studio Code	C++ 编辑器
LeetCode	刷题平台

🧠 学习建议

阶段	推荐内容
新手	插入排序基础
进阶	动态数组的应用
高手	排序算法优化与时间复杂度分析

📅 最后更新时间：2025年5月22日 22:09

🎉 祝你刷题愉快，GESP 顺利通关！🚀

admin SU @ 2025-5-22 22:07:51
B3951 [GESP样题五级] 小杨的队列

涉及的知识点与算法解析

1. 核心算法：插入排序（Insertion Sort）
- 原理：
  插入排序是一种简单直观的排序算法，其核心思想是将未排序部分的元素逐个插入到已排序部分的正确位置。每次插入新元素时，从后向前扫描已排序部分，找到合适的位置并插入。
- 与本题的关联：
  题目要求每次插入新同学后，队列按身高排序。此时队列的其余部分已经有序，因此只需将新同学插入到正确位置。代码中模拟了插入排序的过程：
  
  将新同学插入到队列末尾。
  
  从前往后扫描队列，将比新同学高的同学与新同学交换位置。
  
  交换次数即为新同学插入到正确位置所需的最小交换次数。
- 代码实现：
  
  for (int j = 0; j < len - 1; ++j) { if (b[j] > b[len - 1]) { swap(b[j], b[len - 1]); ++cnt; } }
2. 数据结构：动态数组（Vector）
- 作用：
  使用 vector<int> b 动态维护当前队列。
  
  每次插入新同学时，通过 push_back() 将新同学的身高添加到队列末尾。
  
  队列的有序性通过插入排序的逻辑维护。
- 优势：
  
  动态数组支持随机访问，方便扫描和交换操作。
  
  时间复杂度较低（插入排序的 $O(M^2)$ 在 $M \leq 2000$ 的约束下是可行的）。
3. 时间复杂度分析
- 算法复杂度：
  
  每次插入操作的时间复杂度为 $O(k)$ ，其中 $k$ 是当前队列的长度（最多为 $M$ ）。
  
  总共有 $M$ 次插入操作，总时间复杂度为 $O(M^2)$ 。
  
  对于 $M \leq 2000$ ， $2000^2 = 4,000,000$ 次操作完全可以在时间限制内完成。
- 空间复杂度：
  
  存储队列的空间为 $O(M)$ ，存储初始身高数组的空间为 $O(N)$ ，总空间复杂度为 $O(N + M)$ 。
4. 其他相关知识点

4.1 交换次数的数学意义
- 最少交换次数的计算：
  每次插入新同学后，最少交换次数等于新同学前面比它高的同学的数量。
  
  例如，队列 [170, 160] 插入 168 后，需要交换一次（170 与 168 交换）。
  
  这与插入排序中“将新元素插入到已排序部分”的逻辑一致。
4.2 输入输出处理
- 输入格式：
  
  读取同学数量 $N$ 和身高数组 $a$ 。
  
  读取点名次数 $M$ 和每次点名的学号 $x$ 。
- 输出格式：
  
  每次插入后输出交换次数 cnt。
5. 可能的优化方向

5.1 二分查找插入位置
- 优化思路：
  如果仅需计算交换次数而不实际移动元素，可以通过二分查找确定新同学在有序队列中的插入位置。
  
  交换次数 = 插入位置前比新同学高的同学数量。
  
  但题目要求输出交换次数，实际需要模拟交换过程，因此此优化无法直接应用。
5.2 使用更高效的排序算法
- 适用场景：
  如果队列规模较大（如 $M > 10^5$ ），插入排序的 $O(M^2)$ 复杂度会超时。此时可考虑更高效的排序算法（如快速排序、归并排序）。
- 本题限制：
  由于 $M \leq 2000$ ，插入排序的效率已经足够。
6. 总结

本题的核心知识点和算法包括：
1. 插入排序：通过模拟插入排序的逻辑，计算每次插入新同学后的交换次数。
2. 动态数组（Vector）：用于维护队列的动态变化。
3. 时间复杂度分析：确保算法在题目约束下运行高效。
4. 输入输出处理：正确读取输入并输出结果。
通过结合插入排序的思想和动态数组的实现，可以高效解决本题。
admin SU @ 2025-5-22 22:06:02
B3951 [GESP样题五级] 小杨的队列

题目解析

核心思路

每次插入新同学后，队列需要重新排序。由于每次插入后队列中的其他同学已经有序，因此只需要将新同学插入到正确的位置。此时，最少交换次数等于新同学前面比它高的同学的数量。

算法原理
- 插入排序思想：每次将新同学插入到队列末尾，然后从前往后扫描，将比新同学高的同学与新同学交换，直到新同学到达正确的位置。
- 时间复杂度：每次插入操作需要 $O(k)$ 的时间（ $k$ 为当前队列长度），总共有 $M$ 次插入操作，总时间复杂度为 $O(M^2)$ ，满足题目约束条件。
代码实现
```
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    int M;
    cin >> M;
    vector<int> b;  // 当前队列

    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        b.push_back(a[x]);  // 插入新同学到队尾

        int cnt = 0;  // 交换次数
        int len = b.size();

        // 从前往后扫描，将比当前元素大的元素交换到后面
        for (int j = 0; j < len - 1; ++j) {
            if (b[j] > b[len - 1]) {
                swap(b[j], b[len - 1]);
                ++cnt;
            }
        }

        cout << cnt << endl;
    }

    return 0;
}
```
代码解释
1. 输入处理：
  
  读取同学数量 $N$ 和每个同学的身高数组 $a$ 。
  
  读取老师点名次数 $M$ 和每次点名的学号 $x$ 。
2. 队列维护：
  
  使用 vector<int> b 动态维护当前队列。
  
  每次插入新同学的身高到队列末尾。
3. 排序与交换：
  
  从队列的起始位置开始，将比新同学高的元素交换到队列末尾。
  
  记录交换次数 cnt，即为当前操作所需的最少交换次数。
4. 输出结果：
  
  每次操作后输出交换次数 cnt。
示例解析

样例 1

输入：
```
5
170 165 168 160 175
4
0
3
2
1
```
输出：
```
0
1
1
2
```
解析：
- 插入 0 号同学（170）：队列 [170]，无需交换。
- 插入 3 号同学（160）：队列 [170, 160]，交换 170 和 160，交换次数为 1。
- 插入 2 号同学（168）：队列 [160, 170, 168]，交换 170 和 168，交换次数为 1。
- 插入 1 号同学（165）：队列 [160, 168, 170, 165]，交换 168 和 165，再交换 170 和 165，交换次数为 2。
样例 2

输入：
```
4
20 20 20 10
4
0
1
2
3
```
输出：
```
0
0
0
1
```
解析：
- 插入 0 号同学（20）：队列 [20]，无需交换。
- 插入 1 号同学（20）：队列 [20, 20]，无需交换。
- 插入 2 号同学（20）：队列 [20, 20, 20]，无需交换。
- 插入 3 号同学（10）：队列 [20, 20, 20, 10]，交换 20 和 10，交换次数为 1。
总结

本题的关键在于理解每次插入新同学后，队列的其余部分已经有序。通过模拟插入排序的思想，我们可以高效计算每次插入所需的最少交换次数。该方法时间复杂度为 $O(M^2)$ ，完全满足题目要求。