[NOI.AC#32]sort 构造

50分做法(只有0,1)

根据归并排序的思想，假设我们现在已经把 \(l\dots mid\) 和 \(mid+1\dots r\) 排好序

只要把左边连续的1和右边连续的0翻转即可

inline bool check(int l,int r){REP(i,l+1,r)if(a[i-1]>a[i])return 0;return 1;}

inline void reverse_sort(int l,int r){

	if(check(l,r))return;

	int mid=l+r>>1,p=l,q=r;

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

	while(p<=mid&&!a[p])++p;

	while(q>mid&&a[q])--q;

	if(p<=mid&&q>mid)printf("%d %d\n",p,q),reverse(a+p,a+q+1);

}

100分做法

回忆一下快排（下面是我1年前写的随机快排）：

void qsort(int l,int r){

    int mid=a[l+rand()%(r-l+1)],x=l,y=r;

    do{

        while(a[x]<mid)++x;

        while(a[y]>mid)--y;

        if(x<=y){

            int temp=a[x];

            a[x]=a[y];

            a[y]=temp;

            ++x;--y;

        }

    }

    while(x<=y);

    if(x<r)qsort(x,r);

    if(y>l)qsort(l,y);

}

快排时，先找一个基准点 \(mid\) ,把大于 \(mid\) 的放到右边，小于等于 \(mid\) 的放到左边

利用这个和刚刚只有0/1的归并排序思路

我们找基准点 \(mid\) 之后，把小于等于 \(mid\) 的数当做0 把大于 \(mid\) 的数当做1 做上面的归并排序，就可以实现大于 \(mid\) 的放到右边，小于等于 \(mid\) 的放到左边 ，和快速排序一样

#include<bits/stdc++.h>

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

#define dbg(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

typedef long long ll;

typedef unsigned int uint;

typedef unsigned long long ull;

typedef pair<int,int>pii;

inline int read(){char c,p=0;int w;

	while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();

	for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;

}

const int N=5e4+5;

int n,a[N];

inline bool check(int l,int r){REP(i,l+1,r)if(a[i-1]>a[i])return 0;return 1;}

void reverse_sort(int l,int r,int x){

	if(l==r)return;

	int mid=l+r>>1,p=l,q=r;

	reverse_sort(l,mid,x),reverse_sort(mid+1,r,x);

	while(p<=mid&&a[p]<=x)++p;

	while(q>mid&&a[q]>x)--q;

	if(p<=mid&&q>mid)printf("%d %d\n",p,q),reverse(a+p,a+q+1);

}

void solve(int l,int r){

	if(check(l,r))return;

	int x=a[l+rand()%(r-l+1)];

	reverse_sort(l,r,x);

	REP(i,l,r)if(a[i]>x)return solve(l,i-1),solve(i,r);

	solve(l,r);

}

int main(){

	srand(19260817);

	n=read();

	REP(i,1,n)a[i]=read();

	solve(1,n);puts("-1 -1");

	return 0;

}

巴特西

[NOI.AC#32]sort 构造

50分做法(只有0,1)

100分做法

最新文章

热门文章