B3951 [GESP样题 五级] 小杨的队列

B3951 [GESP样题 五级] 小杨的队列

题目意思是每次有一个人从队尾进入队列，随后这个队列可以根据交换，使得队列变成从小到大的排序。
注意这个交换时可以选择两个下标a和j交换他们两人的位置。

当时第1次看错了，所以就以为是模拟冒泡排序，就写了一个upper_bound来寻找有多少个比它大的元素，比新来的大的元素个数就是对答案的贡献。
这个如果在没有重复身高的人的条件下，其实也是对的，但是对于有重复身高的人就会出错。
但是想了想，发现可以打个补丁。就是我们可以对新的队列里面的元素进行去重，去重完之后就消除了重复元素对答案的影响。
代码如下

#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int a[N],b[N];
int n,m,cnt = 0;
int main()
{map<int,int>mp;cin>>n;for(int i = 0 ; i < n ; ++i)cin>>a[i];cin>>m;for(int i = 0 ; i < m ; ++i){int x;cin>>x;int pos = upper_bound(b+1,b+1+cnt,a[x]) - b;
//         cout<<pos<<" ";cout<<cnt-pos+1<<endl;if(mp[a[x]] == 0){b[++cnt] = a[x];mp[a[x]]++;sort(b+1,b+1+cnt);}}return 0;
}

但是很显然，五级的考纲里面没有map，所以想了一下，发现正确做法也挺妙的。
我们注意到这个队列，在每次进入一个人之后，都会进行调整，变成从小到大排列的情况。
也就是小的排在前面，最大的排在最后面。
那么我们其实可以对每一个元素进行比较：将前面的元素和新加进来的元素比较，如果有大于新的元素的，就把这个大的放在最后面，同时答案加一，这样就可以得到最后的从小到大的排序。

#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int a[N],b[N];
int n,m;
int main()
{cin>>n;for(int i = 0 ; i < n ; ++i)cin>>a[i];cin>>m;for(int i = 0 ; i < m ; ++i){int cnt = 0;int x;cin>>x;b[i] = a[x];
//         cout<<b[i]<<endl;for(int j = 0 ; j < i ; ++j)if(b[j] > b[i])swap(b[j],b[i]),cnt++;cout<<cnt<<endl;}return 0;
}