Out of Stops
题面


题意
一组无序的数字，如果需要使用m次冒泡排序法才能把这一组数字排成递增数列的话就输出m+1

分析
可能大多数人一上来就想用冒泡排序来模拟一下，也就是两个for循环。但是细心的你肯定发现这道题的n最大值为1e5，所以o(n^2)就是1e10，远大于1s可以承受的范围，所以我们必须换一个思路。你自己在脑海里模拟一下冒泡排序的过程，每一次过程是不是小的数往前移动有且只能移动一次?所以我们就可以使用以动化静的思想来处理这道题。
具体步骤

  1. 利用pair数据结构把目前无序的数的位置与数字对应起来。
  2. 根据数字的大小利用sort函数从小到大排序，如果两个数的大小相同，就把其中一个数位置小的排在前面。
  3. 这时排序好的数字也会增添一个新的位置，也就是从小到的顺序 1 2 3 4 5…
  4. 利用max（之前位置-现在位置）就是冒泡排序所使用的次数
    举例说明
    5个数 2 4 4 3 1
    2–>1 排序后 1–>1
    4–>2 2–>2
    4–>3 3–>4
    3–>4 4–>5
    1–>5 4–>6
    合并之后
    1–>5(之前位置)–>1（之后位置）
    2–>1 -->2
    3–>4 -->4
    4–>2 -->5
    4–>3 -->6
    左边减去右边的最大值就是4
    所以ans就是5.
    思路就是每次冒泡排序只是左移，看左移的最大容量
    AC代码 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100000+5;
typedef pair<int,int> P;
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=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++){
	ans=max(ans,p[i].second-i);
}
cout<<ans+1<<endl;
return 0;
}