历年北京师范大学计算机保研机试真题
本文整理北京师范大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
队伍最少交换次数
题目描述
本来是一个已经按身高升序排列好的队伍，突然中间有一个人插队了。每次只能进行相邻的一对一调整，问最少需要几次这样的相邻交换可以把队伍重新调整回有序。
输入格式
输入包含三行：
第一行：原升序队列（用空格分隔的整数）
第二行：插入的数字（整数）
第三行：插队后的队列（用空格分隔的整数）
输出格式
输出一个整数，表示最少需要的相邻交换次数。
数据范围
-
队列长度不超过 $10^5$
-
队列中的数字均为整数，且保证插入后队列是原队列插入一个数字的结果
输入样例1
1 2 3 5 6
4
1 4 2 3 5 6
输出样例1
2
输入样例2
1 2 3 4
5
1 2 3 4 5
输出样例2
0
数组拆分
题目描述
给你一个长度为 $n$ 的数组 $A$，你需要将数组分成两个组（每个元素必须恰好属于一个组），使得两个组的和的差的绝对值最小。输出这个最小差值。
输入格式
第一行一个整数 $n$，表示数组长度。
第二行 $n$ 个整数，表示数组 $A$。
输出格式
对于每个测试用例，输出一个整数，表示最小差值。
输入样例1
4
1 2 3 4
输出样例1
0
输入样例2
5
1 6 17 11 5
输出样例2
4
面试安排问题
题目描述
你作为面试官，每次只能面试一个人。已知总共有 $n$ 个人，每个人的到达时间和面试所需时间。你需要安排面试顺序，使得所有人面试结束的时刻尽可能早。假设面试必须按照到达顺序进行（即先到先面试），但如果面试官正在面试，后到的人需要等待。问所有人面试结束的最短时间是多少。
输入格式
第一行一个整数 $n$，表示人数。
第二行 $n$ 个整数，表示每个人的到达时间。
第三行 $n$ 个整数，表示每个人的面试时长。
输出格式
一个整数，表示所有人面试结束的最早时刻。
输入样例1
3
0 1 3
3 9 2
输出样例1
14
输入样例2
5
0 0 2 4 5
2 1 1 1 1
输出样例2
6
拼接数字大串的第k位
题目描述
把所有非负整数顺序拼接成一个字符串，如 $01234567891011121314...$
给你若干次查询，每次输入一个正整数 $k$，问这个长字符串的第 $k$ 位（下标从 $1$ 开始）是什么数字。
输入格式
第一行输入 $t$（查询次数）
接下来 $t$ 行，每行一个正整数 $k$
输出格式
输出 $t$ 行，每行一个数字，表示对应查询的结果。
输入样例1
3
1
10
12
输出样例1
0
9
0
G/H串前缀翻转
题目描述
$Farmer John$ 想把他的 $N$ 头奶牛排成一排（$N$ 为偶数），使得尽可能多的更赛牛（$G$）处于偶数位置（下标从1开始，即位置 $2, 4, 6, \dots$）。
他可以进行若干次操作，每次可以将队伍的一个偶数长度前缀（即前 $2, 4, 6, \dots$ 头牛）翻转。求要达到最多偶数位 $G$ 时，所需的最小翻转次数。
输入格式
第一行输入一个整数 $N$（$2 \leq N \leq 2 \cdot 10^5$），表示奶牛的数量（保证为偶数）。
第二行输入一个长度为 $N$ 的字符串，仅包含字符 'H' 和 'G'。
输出格式
输出一个整数，表示所需的最小翻转次数。
输入样例1
14
GGGHGHHGHHHGHG
输出样例1
1