题解 P4375 【[USACO18OPEN]Out of Sorts G】

· · 题解

点我了解详情(´▽`)ﾉ <!--more-->

推荐我的博客

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。

首先读题，知道他想让你做什么。

奶牛的代码就是问你如果把冒泡排序该成双向的要排几次。

如果普通的冒泡，那么他的遍数= max {1，每个数前面有几个比它大}；

因为你每次会把一个比某个数小的数移到这个数后面。

我们先离散化，每个数的值为他的排名，就是第几大。

例如 100 1000 10000离散化后是1 2 3；

同理我们可以得到双向冒泡排序遍数=max{前?个位置上值>?的数有多少个，1}

注意它和普通冒泡排序的不同。

为什么结论是这个？

因为对于每个?

  1. 向后扫会保证把前 ? 个位置上一个值> ? 的数扔到后边去
  2. 向前扫会保证被换到前? 个位置上的新数的值是≤ ? 的

如果不懂可以看下面。

拿样例举例

5

1 8 5 3 2

离散化后 1 5 4 3 2

位置为  1 2 3 4 5

例如i=3

前3个数分别是1 5 4

5和4>3

后两个数分别是 3 2

3 2<=3

所以我们就换了两次。

然后我们就可以模拟了。

懒得模拟写树状数组也行。

#include <cstdio>
#include <algorithm> 

using namespace std;
const int N=100005;

struct data
{
    int val,num;
    friend bool operator <(data x,data y){if(x.val==y.val)return x.num<y.num;return x.val<y.val;}
}a[N];
int n,ans=1,cnt;
int vis[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].num=i;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(i<a[i].num) cnt++;
        if(vis[i]) cnt--;
        vis[a[i].num]=true;
        ans=max(ans,cnt);
    }
   printf("%d",ans);
}