传送门：https://www.luogu.org/problemnew/show/P4378
题目大意：
给一串数字，问经过以下伪代码冒泡排序后，moo了多少次。
sorted = false while (not sorted): sorted = true moo for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] sorted = false 12345678
思路：一个数字在它应在的位置后面，它应该往前移动，每moo一次往前移动一格（因为一定有比它大的数字在它前面，所以一定会发生交换），直到在它应在的位置，答案即为所有位于应在的位置后面的数字跟它应在的位置的距离差的最大值+1，由于有相同数字，冒泡排序是稳定排序，相同数字排序后先后顺序不变，排序时应用stable_sort()而不是不稳定的sort()
代码：
#include <bits/stdc++.h> #define ll long long using namespace std; const ll M=100000+10; ll n; struct aa{ll id,num; }a[M]; bool cmp(aa x,aa y){return x.num<y.num; } int main(){cin>>n;ll mini,ans=0;for(ll i=0;i<n;i++) cin>>a[i].num,a[i].id=i;stable_sort(a,a+n,cmp);for(ll i=0;i<n;i++){ans=max(ans,max(0LL,a[i].id-i));}cout<<ans+1;return 0; }
12345678910111213141516171819202122
