首页 > 代码库 > 51nod1364 最大字典序排列

51nod1364 最大字典序排列

不断的在cur的后面找最大的符合条件的数扔到cur的前面。 用线段树维护操作就可以了。

#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define lson l,mid,x<<1#define rson mid+1,r,x<<1|1int read(){	int x=0;char c=getchar();	while(!isdigit(c)) c=getchar();	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();	return x;}const int nmax=1e5+5;int a[nmax],mx[nmax<<2],pos[nmax<<2],sm[nmax<<2];void pushup(int x){	int a=x<<1,b=x<<1|1;	sm[x]=sm[a]+sm[b];	if(mx[a]<mx[b]) mx[x]=mx[b],pos[x]=pos[b];	else mx[x]=mx[a],pos[x]=pos[a];}void build(int l,int r,int x){	if(l==r){		mx[x]=a[l],pos[x]=l,sm[x]=1;return ;	}	int mid=(l+r)>>1;build(lson);build(rson);	pushup(x);}struct node{	int mx,pos;	node(int mx,int pos):mx(mx),pos(pos){};	node(){};};int query(int l,int r,int x,int p){	if(l==r) return l;	int mid=(l+r)>>1;	if(p<=sm[x<<1]) return query(lson,p);	return query(rson,p-sm[x<<1]);}int query_sm(int l,int r,int x,int tl,int tr){	if(tl<=l&&tr>=r) return sm[x];	int mid=(l+r)>>1,ans=0;	if(tl<=mid) ans+=query_sm(lson,tl,tr);	if(tr>mid) ans+=query_sm(rson,tl,tr);	return ans;}node query_mx(int l,int r,int x,int tl,int tr){	if(tl<=l&&tr>=r) return node(mx[x],pos[x]);	int mid=(l+r)>>1;node ans=node(0,0),t;	if(tl<=mid) ans=query_mx(lson,tl,tr);	if(tr>mid) {		t=query_mx(rson,tl,tr);		if(t.mx>ans.mx) ans=t;	}	return ans;}void del(int l,int r,int x,int p){	if(l==r) mx[x]=pos[x]=sm[x]=0;	else{		int mid=(l+r)>>1;		p<=mid?del(lson,p):del(rson,p);		pushup(x);	}}int main(){	int n=read(),m=read();	rep(i,1,n) a[i]=read();	build(1,n,1);	int cur=1,u,v,d,tmp,temp,cnt=0;node o;	rep(i,1,n){		if(++cnt>n) break;		u=query(1,n,1,m+1);		o=query_mx(1,n,1,i,u);		printf("%d\n",o.mx);		del(1,n,1,o.pos);		m-=query_sm(1,n,1,1,o.pos);		if(o.pos!=i) --i;	}	return 0;}

  

1364 最大字典序排列技术分享
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
技术分享 收藏
技术分享 关注
给出一个1至N的排列,允许你做不超过K次操作,每次操作可以将相邻的两个数交换,问能够得到的字典序最大的排列是什么?
例如:N = 5, {1 2 3 4 5},k = 6,在6次交换后,能够得到的字典序最大的排列为{5 3 1 2 4}。
Input
第1行:2个数N, K中间用空格分隔(1 <= N <= 100000, 0 <= K <= 10^9)。第2至N + 1行:每行一个数i(1 <= i <= N)。
Output
输出共N行,每行1个数,对应字典序最大的排列的元素。
Input示例
5 612345
Output示例
53124

51nod1364 最大字典序排列