首页 > 代码库 > Atcoder arc080E Young Maids(线段树+优先队列)
Atcoder arc080E Young Maids(线段树+优先队列)
给出一个n排列，每次可以选择相邻的两个数字放在新的排列首部，问最后形成的新的排列字典序最小是?
考虑新排列的第一个数字，则应是下标为奇数的最小数，下标不妨设为i。第二个数字应该下标大于i且为偶数的最小数，不妨设为j。
那么这样就将[1,n]新分割成了三个区间[1,i-1]，[i+1,j-1]，[j+1,n]。
用线段树实现查询操作。用优先队列维护区间的最优值。
时间复杂度O(nlogn).
# include <cstdio># include <cstring># include <cstdlib># include <iostream># include <vector># include <queue># include <stack># include <map># include <bitset># include <set># include <cmath># include <algorithm>using namespace std;# define lowbit(x) ((x)&(-x))# define pi acos(-1.0)# define eps 1e-8# define MOD 1000000007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FDR(i,a,n) for(int i=a; i>=n; --i)# define bug puts("H");# define lch p<<1,l,mid# define rch p<<1|1,mid+1,r# define mp make_pair# define pb push_backtypedef pair<int,int> PII;typedef vector<int> VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;inline int Scan() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f;}inline void Out(int a) { if(a<0) {putchar(‘-‘); a=-a;} if(a>=10) Out(a/10); putchar(a%10+‘0‘);}const int N=200005;//Code begin....struct qnode{ int l, r, vl, vr; qnode(int _l=0, int _r=0, int _vl=0, int _vr=0):l(_l),r(_r),vl(_vl),vr(_vr){} bool operator<(const qnode &m)const{return vl>m.vl;}};priority_queue<qnode>que;struct Seg{int odd, even;}seg[N<<3];int a[N], id[N];VI ans;void push_up(int p){ seg[p].even=min(seg[p<<1].even, seg[p<<1|1].even); seg[p].odd=min(seg[p<<1].odd, seg[p<<1|1].odd);}void init(int p, int l, int r){ if (l<r) { int mid=(l+r)>>1; init(lch); init(rch); push_up(p); } else { if (l&1) seg[p].even=a[l], seg[p].odd=INF; else seg[p].odd=a[l], seg[p].even=INF; }}int query(int p, int l, int r, int L, int R, int flag){ if (L>r||R<l) return INF; if (L<=l&&R>=r) return flag?seg[p].even:seg[p].odd; else { int mid=(l+r)>>1; return min(query(lch,L,R,flag),query(rch,L,R,flag)); }}int main (){ int n, x, y, l, r, ll; qnode tmp; scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i), id[a[i]]=i; init(1,1,n); x=query(1,1,n,1,n,1); l=id[x]; y=query(1,1,n,l+1,n,0); que.push(qnode(1,n,x,y)); FOR(i,1,n/2) { tmp=que.top(); que.pop(); ans.pb(tmp.vl); ans.pb(tmp.vr); l=id[tmp.vl]; r=id[tmp.vr]; if (tmp.l<l-1) { x=query(1,1,n,tmp.l,l-1,tmp.l&1); ll=id[x]; y=query(1,1,n,ll+1,l-1,(l-1)&1); que.push(qnode(tmp.l,l-1,x,y)); } if (l+1<r-1) { x=query(1,1,n,l+1,r-1,(l+1)&1); ll=id[x]; y=query(1,1,n,ll+1,r-1,(r-1)&1); que.push(qnode(l+1,r-1,x,y)); } if (r+1<tmp.r) { x=query(1,1,n,r+1,tmp.r,(r+1)&1); ll=id[x]; y=query(1,1,n,ll+1,tmp.r,tmp.r&1); que.push(qnode(r+1,tmp.r,x,y)); } } for (int i=0; i<ans.size(); ++i) printf(i==0?"%d":" %d",ans[i]); putchar(‘\n‘); return 0;}
Atcoder arc080E Young Maids(线段树+优先队列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。