[数据结构与算法]蓝桥杯 双向排序【省赛】【研究生组】

?

可以结合AcWing的视频讲解深入理解：?AcWing 3419. 双向排序（蓝桥杯C++ AB组辅导课） - AcWing

C++解答：

#include<iostream>
#include<utility>
#include<algorithm>

using namespace std;

#define N 100010

pair<int, int> stack[N]; //存储可以执行的操作的栈

int ans[N];  // 存储答案 

int main()
{
	int n, m;
	cin>>n>>m;
	int a, b, top = 0;  //top栈顶 
	//需要明白的是，栈内最终存储的是前缀和后缀的交替操作，并且交集部分是递减的 
	while(m --)
	{
		cin>>a>>b;
		if(a == 0)  //前缀降序
		{
			// 将所有相连且相同的操作整合为一个，省略不必要操作
            // 同为前缀，操作坐标小的可以被操作坐标大的代替（内部排序可以被整体排序代替）
            // 同为后缀，操作坐标大的可以被操作左边小的代替
			while(top!=0 && stack[top].first==0)
			{
				b = max(b, stack[top].second);  //保留操作坐标大的 
				top--; //出栈 
			}
			// 若后缀操作前面的前缀操作比当前的前缀操作数小，可以将前、后缀操作均省略（内部排序可以被整体排序代替）
			while(top>=2 && stack[top-1].second<=b)
			{
				top = top - 2;  //出两次栈，相当于同时省略前面的一次前缀和一次后缀操作 
			}
			stack[++top] = make_pair(a, b); //入栈 
		}
		else  //后缀升序 
		{
			if(top != 0)  //第一步有意义的操作肯定是前缀降序(如果第一步是后缀升序，原始数列本来就是升序的) 
			{
				//后缀的情况同理 
				while(top!=0 && stack[top].first==1)
				{
					b = min(b, stack[top].second);
					top--;
				}
				while(top>=2 && stack[top-1].second>=b)
				{
					top = top - 2;
				}
				stack[++top] = make_pair(a, b);
			}
		}
	}
	int k = n;  //用于计数填空ans 
	int l=1, r=n;  //创建左右端点，记录已经排列的坐标
	for(int i=1; i<=top; i++)  //将栈从栈底到栈顶遍历一遍,把栈当作队列使用 
	{
		if(stack[i].first == 0)
		{
			// 若本操作为前缀，操作坐标之后的数就不会再被修改，即可确定进入答案数组
            // 后缀为升序，从后往前即为  k -- 操作
			while(r>stack[i].second && l<=r)
			{
				ans[r--] = k--;
			}
		}
		else
		{
			// 若本操作为后缀，操作坐标之前的数就不会再被修改，即可确定进入答案数组
            // 前缀为逆降，从前往后即为  k -- 操作
            while(l<stack[i].second && l<=r)
            {
            	ans[l++] = k--;
			}
		}
	}
	// 如果序列还没有被遍历完(中间重合部分)，就通过考虑最后的操作是正序还是倒序将剩余的序列排好
    // 因为最先的操作只有是前缀才有效，所有操作均交替进行
    // 可以通过 top % 2 进行判断最后一项操作是什么
    // 如果 top % 2 == 1 ，最后一项是前缀，最后的部分是逆序
    //      top % 2 == 0 ，最后一项是后缀，最后的部分是正序
	if(top%2 == 0)
	{
		while(l<=r)
		{
			ans[r--] = k--;
		}
	}
	else
	{
		while(l<=r)
		{
			ans[l++] = k--;
		}
	}
	for(int i=1; i<=n; i++)
	{
		cout<<ans[i]<<" ";
	}
	return 0;
}