P8445 射命丸文的取材之旅 构造

题目链接

---

思路：

这道题是一道十分经典的将题目简化再处理的题目，我们不难发现首先每个数的范围是在0n，那么可能的mex值则为0n+1。其次我们又会发现处理ai==bi这种情况会影响我们选择mex的值，其他让我们选择的数对我们都可以很容易的让某个数不出现。所以题目转换为被ai==bi划分的片段中，区间长度-mex的最大值。我们可以枚举mex从0~n+1，代码如下

#include<stdio.h>//令ai==bi的时候为间断点，ai!=bi的时候为摇摆点 
int n,a[1000008],b[1000008],end[1000008],ans;
typedef struct a{
	int now_idx;
	int nxt;//上一个间断点结构体在point里的下标 
}id;
id point[1000008];
int point_id;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		if(a[i]==b[i]){
			point[++point_id].now_idx=i;
			point[point_id].nxt=end[a[i]];//end[a[i]]存放的是上次出现相同值的间断点的下标，如果它是第一次出现则end[a[i]]里面存放的是0； 
			end[a[i]]=point_id;
		}
	}
	for(int u=0;u<=n+1;u++){
		if(end[u]==0){
			int ans1=n-u;
			ans=ans>ans1?ans:ans1;
		}
		else{
			int end1=n,i=0;//因为链表是从前向后记的，所以遍历的时候我们从后向前遍历 
			for(i=end[u];i;i=point[i].nxt){
				int idx=point[i].now_idx;
				if(a[end1]==u){//如果当前的右端点是间断点 
					if(end1-1>idx){//两个间断点如果相邻就没有答案 
						int ans1=end1-1-(idx+1)+1-u;
						ans=ans>ans1?ans:ans1;
					}
				}
				else{//如果右端点不是间断点 
					int ans1=end1-(idx+1)+1-u;
					ans=ans>ans1?ans:ans1;
				}
				end1=idx;
			}
			//因为可能第一个间断点之前仍然存在一个区间
			if(end1!=1){
				int ans1=end1-1-1+1-u;
				ans=ans>ans1?ans:ans1;
			} 
		}
	}
	printf("%d",ans);
	return 0;
}