【深基15.例1】询问学号

题意

按进教室顺序给出 n 个学号。每次询问第 i 个进入的学生学号，逐行输出答案。

思路

顺序固定且只查询位置，直接把学号按入场顺序存起来。题目编号从 1 开始，下标从 0 开始，因此查询 position 的答案是 student_ids[position-1]。

注意：n <= 2e6。若写成

python

1data = list(map(int, sys.stdin.buffer.read().split()))

会瞬间创建约 n+m 个 Python int 对象，常数很大，容易在大数据上 TLE / MLE，小样例仍正确，分数常停在 30 分左右。

更稳妥的做法：

sys.stdin.buffer.read().split() 只得到 bytes token；
学号用 array("i", ...) 存成连续整型数组；
查询时再 int(token)，答案用 "\n".join 一次写出。

Python 知识

array("i") 存 32 位有符号整数，比 list[int] 省对象开销。
大数据输入优先 sys.stdin.buffer.read()，避免逐行 input()。
"\n".join(...) 比十万次 print 更适合批量输出。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大量整数 token 与多行输出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13import sys
from array import array


data = sys.stdin.buffer.read().split()
n = int(data[0])
m = int(data[1])

# n 最大 2e6：用 array 存学号，避免 200 万个 Python int 对象拖慢
student_ids = array("i", map(int, data[2 : 2 + n]))

out = [str(student_ids[int(data[2 + n + i]) - 1]) for i in range(m)]
sys.stdout.write("\n".join(out))

cpp

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/**
 * P3156 【深基15.例1】询问学号
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e6 + 5;

// 学号数组，按入场顺序存放，下标从 1 开始
int a[MAXN];
int n, m;

int main() {
    scanf("%d%d", &n, &m);
    // 读入 n 个学号
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    // 处理 m 次询问，题目编号从 1 开始，直接输出 a[query]
    while (m--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", a[x]);
    }
    return 0;
}

Pythonic 写法

下标查询生成器：

python

1
2
3
4
5
6
7import sys
from array import array

data = sys.stdin.buffer.read().split()
n, m = map(int, data[:2])
ids = array("i", map(int, data[2 : 2 + n]))
sys.stdout.write("\n".join(str(ids[int(data[2 + n + i]) - 1]) for i in range(m)))

STL 写法

C++ 里用 vector 保存学号：它的长度在运行时才由输入的 n 决定，不需要事先猜一个上限，正好体现「长度可以变的数组」。读入时按下标 1..n 存放，询问时直接读出 a[x]，和上面 Python 用列表下标查询是同一件事；注意 n 到 2e6，需要快速 IO。

对应的 cppbook 章节：vector：能改变长度的数组

cpp

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/**
 * 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-10-06 23:39
 * update_at: 2026-10-06 23:39
 */

// main-stl.cpp：STL 写法，用 vector 保存学号；vector 的长度由输入的 n 决定，
// 正是“长度可以变的数组”这个教学点。查询直接用下标 a[x] 读出答案。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    // n、m 最大到 2e6 / 1e5，用快速 IO（关同步 + 解绑 cin/cout）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    // vector 的长度在运行时才由 n 决定：开 n+1 个格子，下标 1..n 对应第 1..n 个进入教室的同学
    vector<int> a(n + 1); // 学号在 1..1e9，用 int 存足够
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 每次询问第 x 个进入教室的同学，题目下标从 1 开始，直接读 a[x]
    for (ll i = 1; i <= m; i++) {
        ll x;
        cin >> x;
        cout << a[x] << '\n';
    }

    return 0;
}

复杂度

读入为 $O(n+m)$ ，每个查询 $O(1)$ ；保存数据和答案需要 $O(n+m)$ 空间。

总结

先辨认操作需求：只有按位置查询时，连续列表就是最简单、最高效的数据结构。