2022杭电多校6 L - Loop

input:

2
7 3
1 4 2 1 4 2 4
5 2
4 3 5 4 5

output:

4 4 2 4 2 1 1
5 4 5 4 3

 题目大意：给我们一个序列a，问经过k次操作后通过该序列能形成的序列最大字典序是多少？，操作说明：在序列中指定一段序列[l,r]，让al+1~ar往前移动一步，把原来的al放在现在ar的位置。

解题思路：对于每一次操作我们可以贪心地从前往后找，找到第一个满足ai

上代码：

#include 
#include 
#include 
#include  
using namespace std;
const int N=3E5+10;
int a[N],st[N],b[N],ans[N];
int n,k;
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		cin>>a[i];
		int tt=0,tb=0;
		for(int i=1;i<=n;i++)
		{
			if(tb>=k)
			{
				st[++tt]=a[i];
				continue;
			}
			//维护一个单调递减栈，至于为什么是递减栈，主要看下面单调栈更新操作 
			while(tt&&(tb//要想让字典序尽可能地大，应该将a[i]前面比a[i]小的元素尽可能放到a[i]后面来，留在a[i]前面的应该是大于等于a[i]的数 
				b[++tb]=st[tt--];
			st[++tt]=a[i];
		 } 
		 sort(b+1,b+tb+1,cmp);//b数组中记录的是我们可以通过操作移动到后面的数字 
		 int cnt=0;
		 int i=1,j=1;
		 for(;;)
		 {
		 	if(i>tb||j>tt)
		 	break;
		 	if(b[i]>st[j])//序列的前面尽可能放大数，保证字典序尽可能大 
		 	ans[++cnt]=b[i++];
		 	else
		 	ans[++cnt]=st[j++];
		 }
		 while(i<=tb)
		 ans[++cnt]=b[i++];
		 while(j<=tt)
		 ans[++cnt]=st[j++];
		 for(int i=1;i<=n;i++)
		 {
		 	cout<
		 	if(i
		 	cout<<" ";
		 	else
		 	cout<
		 }
	}
	return 0;
}