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

GESP C++ 五级练习，但是核心的考点是四级排序内容，因为是GESP五级样例，所以归类在五级练习之中，其实四级同学完全可以练习，难度⭐⭐★☆☆。洛谷难度等级普及−

luogu-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 \le N$），表示要求学号为 $x$ 的同学加入队伍。保证该名同学此前不在队伍中。

输出格式

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

输入输出样例 #1

输入 #1

5
170 165 168 160 175
4
0
3
2
1

输出 #1

0
1
1
2

输入输出样例 #2

输入 #2

4
20 20 20 10
4
0
1
2
3

输出 #2

0
0
0
1

说明/提示

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

题目分析

解题思路

题目要求的是“每次点名后，把新同学插入到当前队伍末尾，再按身高升序排序所需的最少交换次数”。本质就是：

1. 维护一个已入队同学的动态有序序列；
2. 每来一个新同学，先放到队尾，再把他冒泡式地往前交换，直到他前面不再有比他高的同学；
3. 交换过程中，每交换一次就累加 1 次答案；
4. 由于身高可能重复，只需保证“相对有序”即可，相同身高无需额外交换。

复杂度

• 每次点名最多把新同学从队尾交换到队头，最坏 $O(M)$ 次交换；
• 共 $M$ 次点名，总体 $O(M^2)$；

边界注意

• 第一个同学直接入队，交换次数为 0；
• 身高重复时，相同身高视为已“有序”，不再往前交换，避免死循环。

示例代码

#include <iostream>
#include <algorithm>

// 存储所有同学的身高，下标即学号
int nums[2005];
// 存储当前已入队同学的身高，按入队顺序排列
int sort_nums[2005];

/**
 * 计算将新入队的同学（位于 sort_nums[target_idx]）通过最少交换插入到已排序片段所需次数
 * 策略：从后往前找到第一个比当前同学高的“不同”身高，每遇到一个就交换并继续前移，直到无法再前移
 * @param target_idx 新入队同学在 sort_nums 中的下标
 * @return 最少交换次数
 */
int get_counts(int target_idx) {
    int count = 0;
    if (target_idx == 0) {
        return 0; // 第一个同学无需交换
    }
    // 从紧邻的前一个位置开始向前扫描
    for (int i = target_idx - 1; i >= 0; i--) {
        // 若当前同学身高更小，且与前一个身高不同（避免重复计数相同身高）
        if (sort_nums[target_idx] < sort_nums[i] && (i == 0 || sort_nums[i] != sort_nums[i - 1])) {
            count++;                     // 需要一次交换
            std::swap(sort_nums[target_idx], sort_nums[i]); // 交换到正确相对位置
            target_idx = i;              // 继续把“新位置”当作 target 前移
        }
    }
    return count;
}

int main() {
    int N;
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::cin >> nums[i]; // 读入每位同学的身高
    }
    int M;
    std::cin >> M;
    for (int i = 0; i < M; i++) {
        int s_num;
        std::cin >> s_num;          // 读入当前被点名的学号
        sort_nums[i] = nums[s_num]; // 把该同学身高加入队伍末尾
        int count = get_counts(i);  // 计算本次最少交换次数
        std::cout << count << std::endl;
    }
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号