题外话:写之前看了一下题解发现我怎么和官方题解一模一样
首先看题.
题意很简单,就是在 \(n\) 的一个排列中找到一段区间满足 \(f_{r-l+1}<Mex({l,r})\) 注意这里的Mex和平时的mex定义不太一样
其中 \(f_i\) 为给定的常数
观察题目所给的式子,不难发现 \(r-l+1\) 其实就是区间长度
那么根据 \(Mex\) 的定义我们可以得出一个结论: \(f_{len}\le len\) 原因很简单,如果不然就算我们将这个区间换为 \(1,2,3...len\)
的话 \(Mex\) 还是无法满足题目中的限制条件.在代码中体现为 if(f[i]>i)continue;
处理了这种情况后,我们开始思考究竟应该怎么样去确定这个区间 \([l,r]\) .
由于左右端点我们均无法确定,于是我们开始思考这个 \(f_i\) 究竟应该如何使用.
就在我们苦思冥想的时候 \(f_i\) 中的 \(i\) 为区间长度并且答案要求输出最小区间长度再次提醒了我们,可能这道题需要使用这个区间长度,从而确定这个区间.
然后我们考虑怎么找到一个 \(Mex\) 大于 \(f_i\) 并且长度不超过 \(i\) 的区间.
发现其实我们需要的不过是 \(1\to i\) 中在原序列中最小和最大的下标这个下标所对应的区间就是我们想要的, 只需要将这个区间长
度和 \(f_i\) 对比即可.
于是我们就恍然大悟了:
定义 \(mi_i\) 表示 \(1 \to i\) 中在原序列下标的最小值
定义 \(ma_i\) 表示 \(1 \to i\) 中在原序列下标的最大值
这里由于原序列是一个 \(n\) 的排列,我们也不用担心下标越界的问题
所以对于每一个 \(i\) 我们只需要判断 \(ma_{f_i}-mi_{f_i}+1\) 和 \(i\) 的大小即可.
若上式小于 \(i\) 则可行.反之则 \(i\) 不是我们想要的答案
至此本题被我们成功地解决啦233.
代码:
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=4e6+5;
const int INF=2147483647;
int n,a[N],pos[N],f[N],ans,mi[N],ma[N];int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[a[i]]=i;}mi[0]=INF;for(int i=1;i<=n;i++){mi[i]=min(mi[i-1],pos[i]);ma[i]=max(ma[i-1],pos[i]);}for(int i=1;i<=n;i++)scanf("%d",&f[i]);for(int i=1;i<=n;i++){if(f[i]>i)continue;if(ma[f[i]]-mi[f[i]]+1<=i){ans=i;break;}}printf("%d\n",ans);return 0;
}
后记:scanf真的比快读慢了好多,以后这种大输入量的题记得使用快读.