题意:有一组数,分别用长度从\([1,n]\)的区间去取子数组,要求取到的所有子数组中必须有共同的数,如果满足条件数组共同的数中最小的数,否则输出\(-1\).
题解:我们先从后面确定每两个相同数之间的距离,然后维护每个\(i\)位置上的数到后面所有相同数的最大距离,然后我们就可以dp来搞了,我从\(1\)开始遍历,如果\(a[i]\)后面的所有相同数间隔的最大距离不大于\(k\),那么说明这个数是满足长度为\(i\)的区间的,我们更新状态\(dp[i]=min(a[i],dp[i])\),否则说明不满足,因为相同\(a[i]\)之间距离大于\(k\),但是我们可以更新当\(k=mxdis[i]\)的时候的状态,即\(dp[mxidis[i]]=min(a[i],mxdis[i])\),另外每次还要和前一位的状态比较一下,因为前面的合法,它在后面也一定合法,所以\(dp[i]=min(d[i],dp[i-1])\).
-
代码:
int t;
int n;
int a[N];
int dp [N]; //dp[i]维护的是长度为i的区间的合法最小元素
int mxdis[N]; //表示当前这个点之后相同点的合法最大区间距离
int dis[N]; //两个相同点之间的距离
int ne[N]; //与自己相同的点的下一个坐标 int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
ne[a[i]]=n+1;
dp[i]=INF;
dis[i]=0;
mxdis[i]=0;
}
dp[0]=INF;
for(int i=n;i>=1;--i){
dis[i]=ne[a[i]]-i;
mxdis[i]=max(dis[i],mxdis[ne[a[i]]]);
ne[a[i]]=i;
}
for(int i=1;i<=n;++i){
dp[i]=min(dp[i-1],dp[i]);
if(mxdis[i]<=i){
dp[i]=min(a[i],dp[i]);
}
else{
dp[mxdis[i]]=min(a[i],dp[mxdis[i]]);
}
}
for(int i=1;i<=n;++i){
if(dp[i]==INF) cout<<-1<<" ";
else cout<<dp[i]<<" ";
}
cout<<'\n';
} return 0;
}