题目背景对应的选择、判断题试题 - GESP 五级样题C 组 - 洛谷有题题目描述小杨的班级里共有 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 次点名每行一个整数 x0≤xN表示要求学号为 x 的同学加入队伍。保证该名同学此前不在队伍中。输出格式输出 M 行依次表示对于每次点名同学们最少要进行几次交换位置才能完成按身高排序的要求。输入输出样例输入 #1复制5 170 165 168 160 175 4 0 3 2 1输出 #1复制0 1 1 2输入 #2复制4 20 20 20 10 4 0 1 2 3输出 #2复制0 0 0 1说明/提示对于所有的测试点保证 1≤M≤N≤2000。对于 50% 的测试点保证所有同学的身高互不相同。代码实现#include iostream #include vector #include algorithm using namespace std; int main() { int N; cin N; vectorint h(N); for (int i 0; i N; i) cin h[i]; int M; cin M; vectorint cur; while (M--) { int x; cin x; cur.push_back(h[x]); vectorint tmp cur; sort(tmp.begin(), tmp.end()); int res 0; vectorbool used(cur.size(), false); for (int i 0; i cur.size(); i) { for (int j 0; j tmp.size(); j) { if (!used[j] tmp[j] cur[i]) { used[j] true; if (i j) res i - j; break; } } } cout res endl; } return 0; }这个算法我写的不是很好有时间限制嵌套循环有点麻烦了时间复杂度上有点高了有更好的算法的同学可以分享一下。