NOI.AC 32 Sort—

从全是0和1的情况入手，可以像线段树一样分治下去，回到本层的时候就是左半部的右边是1，右半部的左边是0，把这两部分换一下就行。代价和时间一样是nlogn。

不全是0和1，可以像快速排序一样，先找一个基准，然后小于它的是0、大于它的是1，调用上一行的那个函数；本层弄好0和1以后，递归到全是0的部分和全是1的部分即可。这样代价和时间都是nlog^2n。

那个基准找得不好的话，一不小心就陷入死循环。所以自己还专门unique了一下，确保不会递归到自己。不过还是很心虚。

看别人有很好的写法，就是以基准（它的值也是中间位置的值，但不用unique）为mid，调用另一个和递归自己的范围就都可以是 l,mid-1 和 mid+1,r 了，这样就不会死循环。而且那个人没有返回那个0和1的边界，而是每次现从mid开始找；只是觉得这样写法扩展自己思路。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=5e4+;

int n,a[N],tmp[N],top;

bool b[N];

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return fx?ret:-ret;

}

int deb;

int calc(int l,int r)

{

//    if(deb<=30)printf("calc l=%d r=%d bl=%d\n",l,r,b[l]),deb++;

    int p=r+;

    for(int i=l;i<=r;i++) if(b[i]){p=i;break;}

    if(p>r) return p-;//all 0

    p=l-;

    for(int i=l;i<=r;i++) if(!b[i]){p=i;break;}

    if(p<l)return p;//all 1

    int mid=l+r>>;

    int p0=calc(l,mid),p1=calc(mid+,r);

//    if(deb<=30)printf("calc:l=%d r=%d p0=%d p1=%d ",l,r,p0,p1);

    if(p0+<p1)

    {

        printf("%d %d\n",p0+,p1);

        for(int i=p0+,j=p1;i<j;i++,j--)

            swap(a[i],a[j]),swap(b[i],b[j]);

    }

    p=r+;

    for(int i=l+;i<=r;i++) if(b[i]){p=i-;break;}

//    if(deb<=30)printf("p=%d\n",p);

    return p;

}

void solve(int l,int r)

{

    if(l>=r)return;

    bool flag=;

    for(int i=l+;i<=r;i++) if(a[i]!=a[i-]){flag=;break;}

    if(!flag)return;

    top=;

    for(int i=l;i<=r;i++) tmp[++top]=a[i];

    sort(tmp+,tmp+top+);

    top=unique(tmp+,tmp+top+)-tmp-;//

    int base=tmp[top>>];

//    if(deb<=30)printf("base=%d\n",base);

    for(int i=l;i<=r;i++)

        b[i]=(a[i]>base);//配合下取整的top

/*    if(deb<=30)

    {

        printf("psol ");

        for(int i=l;i<=r;i++)printf("%d ",b[i]);

        printf("\n\n");

    }

*/

//    if(deb<=30)printf("solve l=%d r=%d\n",l,r);

    int d=calc(l,r);

//    if(deb<=30)printf("d=%d\n",d);

/*

    if(deb<=30)

    {

        printf("csol ");

        for(int i=l;i<=r;i++)printf("%d ",b[i]);

        printf("\n\n");

    }

*/

    solve(l,d); solve(d+,r);

}

int main()

{

    n=rdn();

    for(int i=;i<=n;i++) a[i]=rdn();

    solve(,n);

    printf("-1 -1\n");

    return ;

}

巴特西

NOI.AC 32 Sort——分治

最新文章

热门文章