2021牛客暑期多校训练营2 K：Stack （构造）

Bertha 。 2022-09-02 00:51 86阅读 0赞

### 题目大意 ###

[原题链接：K：Stack][K_Stack]  
给你一个b序列中的k个位置的数，让你构造一组满足要求的a序列，其中bi代表a数组中第i个数作为结尾的最大上升子序列的长度为bi，而a数组是一个1-n的全排列，每个数不重复。若无法构造，输出-1。

--------------------

### 思路 ###

首先我们假设先不考虑a数组是一个全排列，即不用管**不重复**的问题，那我们首先将所有已给的k个数放在他相应的位置。然后将其他没确定的数，从前往后依次给定，我们给他赋值为前一个数加一。这样我们确定的一个序列一定是满足题意的，只是会有数字重复。  
举个例子，加入我们给定b的第四位是1，第五位是2，那我们通过上述方法能得到序列：1 2 3 1 2 2，我们发现这个序列就是满足要求的，因为我们只是构造1.2.3…这样的简单序列，并且满足他所给定的k个位置的要求。  
那么接下来我们只需要在把**不重复**这个条件加进去就好了。我们用一个栈stk来从后往前处理。因为前面数的结果不会影响到后面的数，而后面的数会影响到前面数的结果，比如后面来一个更小的数，就会影响到前面的结果。我们用一个val来计唯一的数值（从1开始，从小往大），如果bi>stk栈中数的个数，我们就一直入栈，直到bi=stk中的数个数，这样栈中的数猜会满足我们当前bi所需要的结果，然后给bi分配栈顶元素，栈顶出栈，继续往前。  
我们还要考虑一个合法性的判断，每一位的bi一定不会币前一位大超过1，即 b i − b i − 1 > 1 b\_i-b\_\{i-1\} > 1 bi−bi−1>1时，时非法的，直接输出-1即可，因为此时只增加了一位数，却在结果中增加了大于1个的数，此时一定非法，其他情况都合法。  
用上述方法首先因为val的原因，不会出现相同的数，而且对于每一位的bi，我们都在栈中放了满足该bi所需要的数，然后再往前分配，这样出来的结果一定是合理的，如果不明白没关系，看着代码手推一遍很快就懂了，下面 是代码。

--------------------

### AC代码 ###

#include<iostream>
    using namespace std;
    const int N = 1000010;
    
    int n,k,top,val,a[N],b[N],stk[N];
    
    int main()
    { 
    	cin >> n >> k;
    	while(k--)
    	{ 
    		int x,p;
    		cin >> x >> p;
    		b[x] = p;
    	}
    	for(int i = 1;i <= n;i++)
    	{ 
    		if(b[i] == 0)
    			b[i] = b[i-1] + 1;		//不考虑重复，构造完b数组
    		else
    			if(b[i] - b[i-1] > 1)
    			{ 
    				cout << -1 << endl;
    				return 0;
    			}
    	}
    	for(int i = n;i > 0;i--)		//根据b数组用stk栈来分配val到a数组
    	{ 
    		while(b[i] > top)		//当前位需要bi个数，因此栈中就放bi个数来满足该位
    			stk[++top] = ++val;
    		a[i] = stk[top--];		//给当前位分配栈顶元素
    	}
    	for(int i = 1;i <= n;i++)
    		cout << a[i] << " ";
    
    	return 0;
    }

[K_Stack]: https://ac.nowcoder.com/acm/contest/11253/K