給你一個1~n的排列p，n是偶數，每次從中任選一對相鄰的數出來，插到排列q的開頭，如此循環，問你所能得到的字典序最小的排列q。

我們先確定q開頭的兩個數q1，q2，q1一定是p的奇數位的最小的數，而q2一定是q1后面最小的偶數位的數，這很顯然。

然后記q1，q2在p中的位置分別是L，R，把p分成三段[1,L],[L+1,R-1],[R+1,n]，遞歸處理，當前區間[l,r]，每次取的一對的左端點L必然是與當前區間左端點l奇偶性相同的最小的數，而R必然是L右側與當前區間左端點l奇偶性不同的最小的數。

可以對奇數位和偶數位分別維護一個線段樹。

重點是輸出答案，我們從前往后構造q，我們發現，所有的數對形成了一個樹形結構，比如說[l,r]，通過之前我們說的過程，取得數對L,R，則[L,R]之間的數對都必須在L,R輸出之后才能輸出，我們把這些數對記作[L,R]的子樹，遞歸把樹建出來。

然后對我們構造出的這棵樹，一開始把所有根的兒子加入堆，我們每次取當前堆里數對左側的數最小的，輸出，然后把它的兒子都加進堆，因為它的所有兒子都“解除了封鎖”。如此直到堆空即可。

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; priority_queue<int,vector<int>,greater<int> >Heap; #define lson rt<<1,l,m #define rson rt<<1|1,m+1,r int v[200005],first[200005],nex[200005],e; void AddEdge(int U,int V){v[++e]=V;nex[e]=first[U];first[U]=e; } int a[200005],cnt,ma[200005],pai[200005]; int minv[2][100005<<4],n,pos[200005]; void update(int o,int p,int v,int rt,int l,int r) {if(l==r){minv[o][rt]+=v;return;}int m=(l+r>>1);if(p<=m) update(o,p,v,lson);else update(o,p,v,rson);minv[o][rt]=min(minv[o][rt<<1],minv[o][rt<<1|1]); } int query(int o,int ql,int qr,int rt,int l,int r) {if(ql<=l&&r<=qr) return minv[o][rt];int m=(l+r>>1);int res=2147483647;if(ql<=m) res=min(res,query(o,ql,qr,lson));if(m<qr) res=min(res,query(o,ql,qr,rson));return res; } void work(int l,int r,int f){if(l>=r){return;}int L=pos[query(l&1,ma[l],(l%2 == r%2) ? ma[r] : ma[r-1],1,1,n/2)];int R=pos[query((L+1)&1,ma[L+1],((L+1)%2 == r%2) ? ma[r] : ma[r-1],1,1,n/2)];pai[a[L]]=a[R];AddEdge(a[f],a[L]);work(l,L-1,f);work(L+1,R-1,L);work(R+1,r,f); } int main(){ // freopen("c.in","r",stdin);scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);pos[a[i]]=i;update(i&1,i/2+(i&1),a[i],1,1,n/2);ma[i]=i/2+(i&1);}if(n==2){printf("%d %d\n",a[1],a[2]);return 0;}work(1,n,0);for(int i=first[0];i;i=nex[i]){Heap.push(v[i]);}while(!Heap.empty()){int U=Heap.top(); Heap.pop();cnt+=2;printf("%d %d%c",U,pai[U],cnt==n ? '\n' : ' ');for(int i=first[U];i;i=nex[i]){Heap.push(v[i]);}}return 0; }

轉載于:https://www.cnblogs.com/autsky-jadek/p/7296626.html

總結

以上是生活随笔為你收集整理的【递归】【线段树】【堆】AtCoder Regular Contest 080 E - Young Maids的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。