题目描述

留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。
她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie最初的对长度为N的数组A进行排序的奶牛码实现。 
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
显然，奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是，Bessie看上去执着于在她的代码中的不同位置使用这个语句。
在用若干个数组测试了她的代码之后，Bessie得到一个有趣的观察现象：大的元素很快就会被拉到数组末尾，然而小的元素需要很长时间“冒泡”到数组的开头（她怀疑这就是为什么这个算法得名的原因）。为了实验和缓解这一问题，Bessie试着修改了她的代码，使代码在每次循环中向前再向后各扫描一次，从而无论是大的元素还是小的元素在每一次循环中都有机会被拉较长的一段距离。她的代码现在是这样的： 
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
给定一个输入数组，请预测Bessie修改后的代码会输出多少次“moo”。

输入描述:

输入的第一行包含。接下来行描述了，每个数都是一个范围为的整数。输入数据不保证各不相同。

输出描述:

输出“moo”被输出的次数。

示例1

输入
5
1
8
5
3
2
输出
2

解答

首先离散化，因为冒泡排序是稳定的排序所以离散化首先是按照价值，如果价值相同按照出现顺序排序
相当于把当前序列最后排序为1、2、3、4、5、6……n  这样的序列
每一趟的冒泡排序会把 i 前面一个比 i 大的数交换到 i 后面，所以我们找出每个数前面比 i 大的数    然后求一个最大  就是冒泡排序的趟数
用树状数组
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int ding=100005;
int b[ding],a[ding],c[ding];
int n;
struct node{
    int id,val;
}init[ding];
 
int lobit(int x){
    return x&(-x);
}
void add(int x){
    while(x<=n){
        b[x]++;
        x+=lobit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>=1){
        ans+=b[x];
        x-=lobit(x);
    }
    return ans;
}
 
//void lsh(){
//  int i;
//  sort(c+1,c+1+n);
//  int cnt=unique(c+1,c+1+n)-c;
//  for(i=1;i<=n;i++){
//      a[i]=lower_bound(c+1,c+1+cnt,a[i])-c;
//  }
//}
bool cmp(node a,node b){
    if(a.val!=b.val)
        return a.val<b.val;
    return a.id<b.id;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int i;
    int ans=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
//      scanf("%d",&a[i]);
        scanf("%d",&init[i].val);
        init[i].id=i;
//      c[i]=a[i];
    }
    sort(init+1,init+n+1,cmp);
    for(i=1;i<=n;i++)
        a[init[i].id]=i;
//  lsh();
    for(i=1;i<=n;i++){
        add(a[i]);
        ans=max(ans,i-sum(i));
         
    }
    printf("%d\n",ans);
 
 return 0;
}

来源：甦萌