首页 > 代码库 > Young Maids
Young Maids
E - Young Maids
Time limit : 2sec / Memory limit : 256MB
Score : 800 points
Problem Statement
Let N be a positive even number.
We have a permutation of (1,2,…,N), p=(p1,p2,…,pN). Snuke is constructing another permutation of (1,2,…,N), q, following the procedure below.
First, let q be an empty sequence. Then, perform the following operation until p becomes empty:
- Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.
When p becomes empty, q will be a permutation of (1,2,…,N).
Find the lexicographically smallest permutation that can be obtained as q.
Constraints
- N is an even number.
- 2≤N≤2×105
- p is a permutation of (1,2,…,N).
Input
Input is given from Standard Input in the following format:
Np1 p2 … pNOutput
Print the lexicographically smallest permutation, with spaces in between.
Sample Input 1
43 2 4 1
Sample Output 1
3 1 2 4The solution above is obtained as follows:
| p | q |
|---|---|
| (3,2,4,1) | () |
| ↓ | ↓ |
| (3,1) | (2,4) |
| ↓ | ↓ |
| () | (3,1,2,4) |
Sample Input 2
21 2
Sample Output 2
1 2
Sample Input 3
84 6 3 2 8 5 7 1
Sample Output 3
3 1 2 7 4 6 8 5The solution above is obtained as follows:
| p | q |
|---|---|
| (4,6,3,2,8,5,7,1) | () |
| ↓ | ↓ |
| (4,6,3,2,7,1) | (8,5) |
| ↓ | ↓ |
| (3,2,7,1) | (4,6,8,5) |
| ↓ | ↓ |
| (3,1) | (2,7,4,6,8,5) |
| ↓ | ↓ |
| () | (3,1,2,7,4,6,8,5) |
//题意：给出一个 p 序列，一个 q 序列，p 中有 1 -- n 的某种排列，q初始为空，现要求可以每次选两个相邻的数，移动到 q 中，要操作到 p 为空，并且要求 q 序列字典序最小
题解：相当难想到的一个题，假如有一个区间 l,r，肯定是，选择这区间内与 l 奇偶相同的，并且最小的作为开头，这样才能保证字典序最小，然后第二个数，应该为选的数右边的，并且与 l 奇偶性不同的，作为第二个，也是为了字典序最小，这部分是标准RMQ问题，随便用什么。然后，区间被分割成最多三块，用优先队列保存区间即可，n*lgn
还是难以想到啊，很好的题
1 # include <cstdio> 2 # include <cstring> 3 # include <cstdlib> 4 # include <iostream> 5 # include <vector> 6 # include <queue> 7 # include <stack> 8 # include <map> 9 # include <set> 10 # include <cmath> 11 # include <algorithm> 12 using namespace std; 13 # define lowbit(x) ((x)&(-x)) 14 # define pi acos(-1.0) 15 # define LL long long 16 17 # define eps 1e-8 18 # define MOD 1000000007 19 # define INF 0x3f3f3f3f 20 inline int Scan() { 21 int x=0,f=1; char ch=getchar(); 22 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} 23 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} 24 return x*f; 25 } 26 inline void Out(int a) { 27 if(a<0) {putchar(‘-‘); a=-a;} 28 if(a>=10) Out(a/10); 29 putchar(a%10+‘0‘); 30 } 31 const int MX=200005; 32 //Code begin.... 33 34 int n; 35 int dat[MX]; 36 int ans[MX]; 37 int mn[MX]; 38 int st[2][MX][40]; 39 struct Qu 40 { 41 int l,r; 42 int dex; //zui xiao ,,biao hao 43 bool operator < (const Qu b) const{ 44 return dat[dex]>dat[b.dex]; 45 } 46 }; 47 void Init() 48 { 49 mn[0]=-1; 50 dat[0]=INF; 51 for (int i=1;i<=n;i++) 52 { 53 if ((i&(i-1))==0) mn[i]=mn[i-1]+1; 54 else mn[i]=mn[i-1]; 55 56 if (i&1) st[1][i][0]=i; 57 else st[0][i][0]=i; 58 } 59 60 for (int j=1;(1<<j)<=n;j++) 61 { 62 for (int i=1;(i+(1<<j)-1)<=n;i++) 63 { 64 if (dat[st[0][i][j-1]]<=dat[st[0][i+(1<<(j-1))][j-1]]) 65 st[0][i][j] = st[0][i][j-1]; 66 else 67 st[0][i][j] = st[0][i+(1<<(j-1))][j-1]; 68 69 if (dat[st[1][i][j-1]]<=dat[st[1][i+(1<<(j-1))][j-1]]) 70 st[1][i][j] = st[1][i][j-1]; 71 else 72 st[1][i][j] = st[1][i+(1<<(j-1))][j-1]; 73 } 74 } 75 } 76 int st_cal(int l,int r,int same) 77 { 78 int k = mn[r-l+1]; 79 int c; 80 if (same) c=l%2; 81 else c=(l+1)%2; 82 83 if (dat[st[c][l][k]]<=dat[st[c][r-(1<<k)+1][k]]) 84 return st[c][l][k]; 85 else 86 return st[c][r-(1<<k)+1][k]; 87 } 88 89 int main() 90 { 91 scanf("%d",&n); 92 for (int i=1;i<=n;i++) 93 dat[i] = Scan(); 94 Init(); 95 priority_queue<Qu> Q; 96 Q.push((Qu){1,n,st_cal(1,n,1)}); 97 int pp=0; 98 for (int i=1;i<=n/2;i++) 99 {100 Qu now = Q.top();Q.pop();101 int ml = now.dex;102 int mr = st_cal(ml+1,now.r,1);103 ans[pp++]=dat[ml];104 ans[pp++]=dat[mr];105 if (ml>now.l)106 Q.push( (Qu){now.l,ml-1,st_cal(now.l,ml-1,1)} );107 if (mr-1>ml)108 Q.push( (Qu){ml+1,mr-1,st_cal(ml+1,mr-1,1)} );109 if (mr<now.r)110 Q.push( (Qu){mr+1,now.r,st_cal(mr+1,now.r,1)} );111 }112 for (int i=0;i<pp-1;i++)113 printf("%d ",ans[i]);114 printf("%d\n",ans[pp-1]);115 return 0;116 }
Young Maids