Codeforces Round #744 (Div. 3) E1. Permutation Minimization by Deque

题目链接

题意大概是给n个不重复元素和一个空双端队列，要求按给出的顺序将这些元素插入队头或队尾，来保证最后得到的队列字典序最小。

思路就是贪心，刚开始用了数组纯暴力模拟的办法。

#include
using namespace std;

#define N 200005

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,i,j;
		int a[N];
		cin>>n;
		int last;
		for(i=0;i>b;
			if(!i) 
			{
				a[0]=b;
				last=b;
			}
			else
			{
				if(b>=last)
				{
					a[i]=b;
				}
				else
				{
					for(j=i;j>0;j--)
					a[j]=a[j-1];
					a[0]=b;
					last=b;
				}
			}
		}
		for(i=0;i 
然后快乐TLE
 
算了算最坏情况下会有O(n2)的复杂度，对于这道题是爆了。
 
遂百度大佬写法，换了双向队列，寄
 
#include
using namespace std;

#define N 200005

deque q;//建立一个双端队列
int a;

int main()
{
	int t,n;
	cin>>t;
	
	while(t--)
	{
		cin>>n>>a;
		q.push_front(a);//插入头部
		for(int i=2;i<=n;i++)
		{
			cin>>a;
			if(a