【深基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)))

复杂度

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

总结

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

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

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结