【题目来源】https://www.luogu.com.cn/problem/B3951【题目描述】小杨的班级里共有 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 行依次表示对于每次点名同学们最少要进行几次交换位置才能完成按身高排序的要求。​​​​​​​【输入样例一】5170 165 168 160 17540321【输出样例一】0112​​​​​​​【输入样例二】420 20 20 1040123​​​​​​​【输出样例二】0001【数据范围】对于所有的测试点保证 1≤M≤N≤2000。对于 50% 的测试点保证所有同学的身高互不相同。【算法分析】代码的核心逻辑‌在于‌维护一个有序序列。‌每当‌插入一个新元素时‌便‌统计当前序列中有多少个已存在的元素比它大。【算法代码】#include bits/stdc.h using namespace std; const int N2e35; int h[N],t[N]; int n,m,x; int main() { cinn; for(int i0; in; i) { cinh[i]; } cinm; for(int i1; im; i) { cinx; t[i]h[x]; int cnt0; for(int j1; ji; j) { if(t[j]t[i]) { swap(t[i],t[j]); cnt; } } coutcntendl; } return 0; } /* in: 5 170 165 168 160 175 4 0 3 2 1 out: 0 1 1 2 */【参考文献】https://www.luogu.com.cn/problem/solution/B3951