首页 > 代码库 > 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 最大字典序排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。