2024北京师范大学保研上机真题
北京师范大学AI夏令营保研上机真题
在线测评链接：https://pgcode.cn/problem

队伍最少交换次数-AI夏令营

题目描述

本来是一个已经按身高升序排列好的队伍，突然中间有一个人插队了。每次只能进行相邻的一对一调整，问最少需要几次这样的相邻交换可以把队伍重新调整回有序。

输入格式

输入包含三行：
第一行：原升序队列（用空格分隔的整数）
第二行：插入的数字（整数）
第三行：插队后的队列（用空格分隔的整数）

输出格式

输出一个整数，表示最少需要的相邻交换次数。

数据范围

• 队列长度不超过 $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

数组拆分-AI夏令营

题目描述

给你一个长度为 $n$ 的数组 $A$，你需要将数组分成两个组（每个元素必须恰好属于一个组），使得两个组的和的差的绝对值最小。输出这个最小差值。

输入格式

第一行一个整数 $n$，表示数组长度。

第二行 $n$ 个整数，表示数组 $A$。

输出格式

对于每个测试用例，输出一个整数，表示最小差值。

输入样例1

4
1 2 3 4

输出样例1

0

输入样例2

5
1 6 17 11 5

输出样例2

4

面试安排问题-AI夏令营

题目描述

你作为面试官，每次只能面试一个人。已知总共有 $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位-AI夏令营

题目描述

把所有非负整数顺序拼接成一个字符串，如 $\mathrm{01234567891011121314...}$

给你若干次查询，每次输入一个正整数 $k$，问这个长字符串的第 $k$ 位（下标从 $1$ 开始）是什么数字。

输入格式

第一行输入 $t$（查询次数）

接下来 $t$ 行，每行一个正整数 $k$

输出格式

输出 $t$ 行，每行一个数字，表示对应查询的结果。

输入样例1

3
1
10
12

输出样例1

0
9
0

G/H串前缀翻转-AI夏令营

题目描述

Farmer John 想把他的 $N$ 头奶牛排成一排（$N$ 为偶数），使得尽可能多的更赛牛（$G$）处于偶数位置（下标从1开始，即位置 $2,4,6,\dots$）。

他可以进行若干次操作，每次可以将队伍的一个偶数长度前缀（即前 $2,4,6,\dots$ 头牛）翻转。求要达到最多偶数位 $G$ 时，所需的最小翻转次数。

输入格式

第一行输入一个整数 $N$（$2\le N\le 2\cdot 10^5$），表示奶牛的数量（保证为偶数）。

第二行输入一个长度为 $N$ 的字符串，仅包含字符 ‘H’ 和 ‘G’。

输出格式

输出一个整数，表示所需的最小翻转次数。

输入样例1

14
GGGHGHHGHHHGHG

输出样例1

1