A. 最大排列

内存限制：512 MiB

时间限制：1000 ms

输入文件：per.in

输出文件：per.out

题目类型：传统

评测方式：文本比较

题目描述

给定1~n的一个排列p。其中n是偶数。

现在你需要重新排列p变成p'，使得p'的字典序尽量大。

但是有一些限制，你重排p的过程必须是这样的：

选择p中任意两个相邻的元素

将p i和p i+1依次插入排列p'的最后

在p中删除p i和p i+1。

请求出字典序最大的可能的p'。

输入格式

从文件 per.in 中读入数据。

第一行包含一个正整数n。

第二行n个数，表示排列p'。

输出格式

输出到文件 per.out 中。

一行 n个数，表示字典序最大的序列p'。

样例

样例输入 1

4

3 1 4 2

样例输出 1

4 2 3 1

样例输入 2

6

6 5 4 1 3 2

样例输出 2

6 5 4 1 3 2

数据范围与提示

对于20%的数据，n<=10；

对于60%的数据，n<=1000；

对于100%的数据，1<=n<=10^5。

下方是我0pts的垃圾代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct node
{
	int l,r,m;
};
node num[N];
int n,maxn,rc,p[N];
int main()
{
	freopen("per.in","r",stdin);
	freopen("per.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i].m;
		num[i].l=i-1;
		num[i-1].r=i;
	}
	num[n+1].l=n;
	num[n].r=n+1;
	for(int i=1;i<=n/2;i++)
	{
		maxn=rc=0;
		for(int j=0;num[j].r<=n;j=num[j].r)
		{
			if(num[j].m>maxn)
			{
				maxn=num[j].m;rc=j;
			}
			else if(num[j].m==maxn&&num[num[j].r].m>num[num[rc].r].m)
			{
				maxn=num[j].m;rc=j;
			}
		}
		p[i*2-1]=num[rc].m;
		p[i*2]=num[rc+1].m;
		num[num[rc].l].r=num[num[rc].r].r;
		num[num[num[rc].r].r].l=num[rc].l;
		maxn=rc=0;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<p[i]<<" ";
	}
	cout<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

但是样例都过了啊！！！为什么一分也没有

求dalao解答，会关注dalao的