CF 1023D. Array Restoration（构造模拟）

CF 1023D. Array Restoration（构造模拟） linking

---

大意：

给定一个长度为 n 的序列。
现在有 q 次 *** 作，对于第 i 次：选定长度不为 0 的一段区间，把区间中的所有值变为 i。
现在对于给定的序列，判断是否由上述 q 次 *** 作得到。
序列中可能有 0，0 可以变成 1~q 中的任意数。

思路：

注意几个点：

1. 不存在中间的元素比两端的小（除去0）： 单调栈，维护单调递增的栈。
   遍历每个位置，如果该元素之前出现过，判断第一个小于等于该元素的值是不是和其相等。 如果不是，说明中间有比其小的，NO。

2. 元素的最大值一定要为 q：
   把一个 0 变为 q。如果没有 0，NO。

3. 最后把 0 都变成相邻元素：
   正着走，反着走，把 0 变为相邻元素。特判全为 0 情况。

Code：

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];

int main(){
	Ios;
	
	cin>>n>>m;
	
	int flag=0, maxa=0;
	for(int i=1;i<=n;i++) cin>>a[i];

	stack stk; //判断是否有中间比两端小的情况 
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0) continue;
		
		while(stk.size() && stk.top() > a[i]) stk.pop();
		
		if(b[a[i]] && stk.top()!=a[i]){
			cout<<"NO";return 0;
		}
		
		stk.push(a[i]);
		
		b[a[i]]++;
	}
	
	for(int i=1;i<=n;i++) maxa=max(maxa,a[i]); //找到最大值 
	
	if(maxa==m) //最大值是m，把0都变成相邻的 
	{
		for(int i=1;i<=n;i++)
			if(a[i]==0) a[i]=a[i-1];
		
		for(int i=n;i>=1;i--){
			if(a[i]==0) a[i]=a[i+1];
		}
		
		for(int i=1;i<=n;i++) if(a[i]==0) a[i]=m;
		
		cout<<"YESn";
		for(int i=1;i<=n;i++) cout<=1;i--) 
			if(a[i]==0) a[i]=a[i+1];
		
		for(int i=1;i<=n;i++) if(a[i]==0) a[i]=m;
		
		cout<<"YESn";
		for(int i=1;i<=n;i++) cout< 
 
改了好久，发现判断中间比两端小的情况判断错了，比两端大的也判断了。。
 改掉之后，超时。
 最后改成单调栈O(n)判断过了。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5698738.html