Out of Sorts II
题面



题意
给你一组无序的数，每次操作是从左向右遍历，如果右边小于左边的话就交换两个值的位置。遍历完之后然后再从右向左遍历，如果右边小于左边的话就交换两个值的位置。这是一次操作，设m次操作后那一组无序的数变成递增的数列，那么就输出m+1。
分析
首先可以确定未排序之前的时候，每一个数对应一个位置。然后把数与位置储存在pair数组里面。通过sort函数，我们可以把数按照递增的顺序排序，然后我们可以看到，如果排完序之后某些数往后移动的话，我们就需要操作1次，并且需要保证这个位置不能再操作，所以使用vis标记。从而就可以得到答案
AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100000+5;
typedef pair<int,int> P;
int vis[maxn];
P p[maxn];//第一个存的是数字，第二个存的是位置
bool cmp(P a,P b){
if (a.first==b.first) return a.second<b.second;
return  a.first<b.first;
}
int main(){
int n,ans=1,cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
	cin>>p[i].first;
	p[i].second=i;
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++){
	if(p[i].second>i) cnt++;
	if(vis[i]) cnt--;
	vis[p[i].second]=1;
	ans=max(ans,cnt);
}
cout<<ans<<endl;
return 0;
}