题目描述
给一个双向冒泡排序的程序：
moo表示输出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]
for i = N-2 downto 0:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = 0 to N-2:
if A[i+1] < A[i]:
sorted = false
再给一个初始的数组。
求把这个数组排好序，输出几次moo
n<=100000,ai<=1e9
题解
考察冒泡排序的本质。
一般的冒泡排序，每次会把最大的数直接沉底，
但是比较小的数，会往前面缓慢冒泡。
具体来说，如果一个数i排名是i，但是位置在i之后，那么，每次循环，i必然会往前面移动一位。
因为必然前面会有一个比i大的数往后沉。
i往前每次移动一次导致复杂度最坏是n^2
swap的次数，就是逆序对数
循环的次数，就是
这个题目，是一个双向的冒泡排序，
对于一个分界点位置i，这个双向排序，每个循环会把一个i之前的大于i的数移到i后面，并且把一个i后面小于i的数移到i的前面。
单向冒泡不能保证每次把一个i后面的小于i的数放到i前面。
排好序是什么意思？
就是说，对于任意的位置i，小于i的数都在i前面，大于i的数都在i后面。
所以 ，我们可以对于所有的位置i，找到i前面比i小的数个数s，i-s就是i位置把小于i的放在i前面，大于i的放在i后面的循环次数。
例如 5 2 3 1 4 双向冒泡可以一次排完。单向冒泡瓶颈在“3”
对于这些次数取一个mx即可。
用树状数组离散化后可以做。
代码：
#include<bits/stdc++.h> using namespace std; const int N=100000+5; int n,ans; int a[N],b[N],cnt[N]; int f[N]; void add(int x){for(;x<=n;x+=x&(-x)) f[x]++;} int query(int x){int ret=0;for(;x;x-=x&(-x))ret+=f[x];return ret;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]);b[i]=a[i]; } sort(b+1,b+n+1);ans=1; for(int i=1;i<=n;i++){ int t=lower_bound(b+1,b+n+1,a[i])-b; //cout<<" tt "<<t<<endl; add(t); cnt[i]=query(i);ans=max(ans,i-cnt[i]); }printf("%d",ans);return 0; }
注意，当数组排好序之后，因为一定要检查一遍，所以moo还是1的。不是0
upda：2019.9.20
这个是通过位置来处理最大值的
还可以通过数值，每个数值每次会有一个在前面且比它大的数放到后面去，而每次会有一个在后面比它小的数到前面去。
同理离散化+树状数组，for i=1~n ans =max(ans,max(number of front and big,number of back and small))