学生排队

GitHub跳转原题关系图Canvas 关系图返回列表

找到指定学号在当前队列的位置，移出后在原位置加移动距离处插回。

OJ: shumeng

题目 ID: CSP201703B

难度:入门

标签:模拟数组

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 朴素做法
    2. 一次到位
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

nn 名学生初始按学号 1,2,…,n1, 2, \ldots, n 从前到后排成一行。进行 mm 次调整，每次给定学号 pp 和移动距离 qq：q>0q > 0 表示该学生向后移动 qq 个位置，q<0q < 0 表示向前移动 −q-q 个位置。输出所有调整结束后的队列。

思路

每次调整只改变一名学生的位置，其余学生的相对顺序不变，因此只需定位该学生并把它移到新位置。

朴素做法

最直观的做法是把目标学生与相邻学生逐次交换，交换次数就是移动距离的绝对值：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
// brute.cpp：逐次交换相邻学生，直接模拟向前或向后移动。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> line(n);
    for (int i = 0; i < n; i++) {
        line[i] = i + 1;
    }

    for (int i = 1; i <= m; i++) {
        int student, move;
        cin >> student >> move;
        int position = 0;
        while (line[position] != student) {
            position++;
        }

        if (move > 0) {
            for (int step = 0; step < move; step++) {
                swap(line[position], line[position + 1]);
                position++;
            }
        } else {
            for (int step = 0; step < -move; step++) {
                swap(line[position], line[position - 1]);
                position--;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << line[i];
    }
    cout << '\n';

    return 0;
}

一次到位

正式实现直接维护当前队列。每次操作先线性查找学号为 pp 的位置 position，把它删除，再插回 position + q 处。这里的 position 是删除前保存的下标：

  • 向后移动 qq：删除后，原来位置 position + 1 \sim position + q 的学生都前移一格，目标学生插回 `position + q$ 恰好到达目的地；
  • 向前移动同样满足这个公式。

题目保证移动合法，且 n,m≤1000n, m \le 1000，因此在数组上做删除和插入已经足够。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> line; // 当前队列，按从前到后的顺序保存学号
    for (int i = 1; i <= n; i++) {
        line.push_back(i);
    }

    for (int i = 1; i <= m; i++) {
        int student, move;
        cin >> student >> move;

        // 在队列中查找该学号当前所在的位置
        int position = 0;
        while (line[position] != student) {
            position++;
        }
        // 先出队，再按移动距离插回。
        // position 是删除前保存的下标：删除后插入到 position + move 正好对应向后/向前移动。
        line.erase(line.begin() + position);
        line.insert(line.begin() + position + move, student);
    }

    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << line[i];
    }
    cout << '\n';

    return 0;
}

复杂度

  • 时间：每次查找、删除和插入均为 O(n)O(n)，总时间复杂度为 O(nm)O(nm)。
  • 空间：保存整个队列，空间复杂度为 O(n)O(n)。

总结

题目给的是学号而不是当前位置，所以每次操作前必须在当前队列重新寻找该学生。删除后按“原下标 + 移动距离”插回，可以统一处理前移和后移，不需要分类讨论。