[noi.ac_D1T2]sort

https://www.zybuluo.com/ysner/note/1289967

题面

定义"翻转排序"：每次操作均为把区间\([l,r]\)中所有数倒过来，即\(swap(a[l],a[r])+swap(a[l+1],a[r-1])+...\)。

每次操作的代价为\(r-l+1\)。

给一个序列\(a\)，用"翻转排序"给它排序，并把代价控制在\(2*10^7\)以内。

\(60pts\) \(n\leq5000\)
\(ex25pts\) \(a[i]\in\{0,1\}\)
\(100pts\) \(n\leq5*10^4\)

解析

感觉很符合\(noip\_T2\)难度。。。

\(60pts\)算法

仔细想想，"翻转"这个条件挺恶心的。

可以不"翻转"吗？那就只能交换相邻两个。

把序列扫\(n\)遍，每次只交换序列中相邻两个数。

这样每交换一次对应着消除一个逆序对，复杂度可控。

次数最多为\((n-1)*[(n-1)-1]/2\leq1.25*10^7\)

但是我并不知道这种排序名字叫什么。。。

复杂度\(O(n^2)\)

代码在下一档。

\(85pts\)算法

这个有点搞笑。

直接归并排序就可以了。

每次归并后把左边的\(1\)区间和右边的\(0\)区间并在一起，翻转即可。

复杂度\(O(nlogn)\)

贴上代码。

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define pc(a) putchar(a)

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1e5+100;

int n,a[N];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void wri(re int x)

{

  if(x>9) wri(x/10);

  pc(x%10+48);

}

il void solve(re int l,re int r)

{

  if(l==r) return;

  if(l==r-1)

  {

    if(a[l]>a[r]) swap(a[l],a[r]),printf("%d %d\n",l,r);

    return;

  }

  re int mid=l+r>>1,p1=0,p2=0;

  solve(l,mid);solve(mid+1,r);

  fp(i,l,mid) if(a[i]==1) {p1=i;break;}

  fp(i,mid+1,r) if(a[i]==1) {p2=i;break;}

  if(!p1) return;

  if(!p2) {printf("%d %d\n",p1,r);reverse(a+p1,a+r+1);return;}

  printf("%d %d\n",p1,p2-1);reverse(a+p1,a+p2);

  return;

}

int main()

{

  n=gi();

  fp(i,1,n) a[i]=gi();

  if(n<=5000)

  {

    fp(i,1,n)

      {

        re int tag=0;

        fp(j,1,n-1)

	  if(a[j]>a[j+1]) tag=1,wri(j),pc(' '),wri(j+1),pc('\n'),swap(a[j],a[j+1]);

        if(!tag) break;

      }

    puts("-1 -1");

    return 0;

    }

  solve(1,n);

  puts("-1 -1");

  return 0;

}

\(100pts\)算法

蒟蒻其实并不知道快排原理

快排的原理是，在向下分治前，先选取一个基准数，通过归并排序，把该分治区间中的小于等于其的数移到左边，大于其的数移到右边。

归并的过程中可以通过"翻转"，把左区间中的大于其的数与右区间中小于等于其的数一次交换完毕。

然后继续向下分治即可。

基准数就是选，该区间中间位置，在排序完后的\(a\)中对应的值。（记得把值离散化）

复杂度\(O(nlog^2n)\)。

很对但是想不到。。。

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1e5+100;

ll n,a[N],b[N];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il int Qsort(re int l,re int r,re ll B)

{

  if(l==r) return l+(a[l]<=B);

  re int mid=l+r>>1,p1=Qsort(l,mid,B),p2=Qsort(mid+1,r,B)-1;

  if(p1!=mid+1&&p2!=mid)

    {

      printf("%d %d\n",p1,p2);

      reverse(a+p1,a+p2+1);

    }

  return p1+(p2-mid);

}

il void solve(re int l,re int r)

{

  if(l==r) return;

  re int mid=l+r>>1;

  Qsort(l,r,b[mid]);

  solve(l,mid);solve(mid+1,r);

}

int main()

{

  n=gi();

  fp(i,1,n) b[i]=a[i]=gi()*n+i;

  sort(b+1,b+1+n);

  solve(1,n);

  puts("-1 -1");

  return 0;

}

巴特西

[noi.ac_D1T2]sort

https://www.zybuluo.com/ysner/note/1289967

题面

解析

\(60pts\)算法

\(85pts\)算法

\(100pts\)算法

最新文章

热门文章