GSEP 5级样题 小杨的队列
题目描述
小杨的班级里共有 N 名同学，学号从 0 至 N - 1。
某节课上，老师要求同学们进行列队。具体来说，老师会依次点名 $M$ 名同学，让他们加入队伍。每名新入队的同学需要先站到队伍末尾（刚开始队伍里一个人都没有，所以第一个入队的同学只需要站好即可），随后，整个队伍中的所有同学需要按身高从低到高重新排序（身高相同的同学之间的顺序任意）。
排队很容易，但重新排序难倒了同学们。稍加讨论后，他们发现可以通过交换位置的方法来实现排序。具体来说，他们可以让队伍中的两名同学交换位置，这样整个队伍的顺序就会发生变化，多经过这样的几次交换后，队伍的顺序就可以排好。
例如：队伍中有 4 名同学，学号依次为 10, 17, 3, 25，我们可以令 3 号同学和 10 号同学交换位置，则交换后的队伍顺序变为 3, 17, 10, 25，这就是一次交换位置。
聪明的小杨想要知道：在老师每次点名一位新同学加入队伍后，在原有队伍的基础上，同学们最少要进行几次交换位置，才能完成老师按身高排序的要求。
输入格式
第一行一个整数 N，表示同学的数量。
第二行 N 个用空格隔开的正整数，依次表示学号为 0, 1, …, N-1 的同学的身高（不超过 2,147,483,647）。
第三行一个整数 M，表示老师点名的数量。
接下来 M 行，依次描述 M 次点名：每行一个整数 x（0 ≤ x ＜ N），表示要求学号为 x 的同学加入队伍。保证该名同学此前不在队伍中。
对于所有的测试点，保证 1≤ M ≤ N ≤ 2000。对于 50% 的测试点，保证所有同学的身高互不相同。
输出格式
输出 M 行，依次表示对于每次点名，同学们最少要进行几次交换位置，才能完成按身高排序的要求。
样例 #1
样例输入 #1
5
170 165 168 160 175
4
0
3
2
1
样例输出 #1
0
1
1
2
样例 #2
样例输入 #2
4
20 20 20 10
4
0
1
2
3
样例输出 #2
0
0
0
1
提示
样例解释1：
初始时队伍为空，身高为 170 的 0 号同学加入队伍，不需要任何交换位置。
接着，身高为 160 的 3 号同学加入队伍的末尾，此时两位同学需要进行依次交换位置，才能保证身高更矮的 3 号同学排在身高更高的 0 号同学前面。
接着，身高为 168 的 2 号同学加入队伍的末尾，此时队伍中的同学学号（身高）依次为 3(160), 0(170), 2(168)，此时 2 号同学可以和 0 号同学进行一次交换位置，即可完成排序要求。
接着，身高为 165 的 1 号同学加入队伍的末尾，此时队伍中的同学学号（身高）依次为 3(160), 2(168), 0(170), 1(165)，此时可以令 1 号同学和 2号同学进行一次交换位置，使队伍变为 3(160), 1(165), 0(170), 2(168)；随后再令 0 号同学和 2 号同学进行一次交换位置，使队伍变为 3(160), 1(165), 2(168), 0(170)，即可完成排序要求。
样例解释2：
前三位加入队伍的同学（0, 1, 2 号同学）身高都相同，不需要进行任何交换位置。最后加入队伍的 3 号同学身高最矮，需要和队头的 0 号同学交换位
置，方可完成排序要求。
#include <iostream>
#include <vector>
using namespace std;
int main() {
uint64_t N; cin >> N; // 总共N个同学
uint64_t a[N]; for (uint64_t i = 0; i < N; i++) cin >> a[i]; // 输入所有身高
uint64_t M; cin >> M; // 输入需要排队的人数
uint64_t b[M] = {0}; // 定义新的排队队列
for (uint64_t i = 0; i < M; i++) { // 排队
uint64_t t; cin >> t; b[i] = a[t]; // 排入队尾
uint64_t ct = 0; // 交换位置的次数
for (uint64_t j = 0; j < i; j++) {
if (b[j] > b[i]){
swap(b[j], b[i]);
++ct;
}
}
cout << ct << endl;
}
}