C. k-Amazing Numbers

Codeforces Round #673 (Div. 2)

题意

给你一个长度为n的数组，让你找到以i为长度的子段中都出现的最小的数(必须每个长度为i的子段都出现)

思路

首先观察题目发现$1\le a[i]\le n\le 3\ast 10^5$,也就是说我们可以通过枚举去解决这个问题，让我们考虑枚举每两个相同数字的之间的最大距离，也就是说这个距离范围内可以包含至少一个这个数。

$ans[i]$长度为$i$的最小的数字为$ans[i]$。

需要特殊考虑的情况是头和尾，因为有的数字可能存中间开始出现。

$vector<int>g[maxn]$通过枚举每个数的下标间距离实现$O(n)$的计算。

需要特别注意的是如果长度小的是$ans[i]$那么大于这个长度的也可以能是$ans[i]$，比如说$ans[2]=4$,$ans[3]=5$,那么$ans[3]=4$也是可以的。

#include<bits/stdc++.h> using namespace std; //#define int long long const int maxn=3e5+10; int ans[maxn],a[maxn]; vector<int>g[maxn]; void solve(){ int n;cin>>n; for(int i=1;i<=n;++i){ g[i].clear();ans[i]=1e9; } for(int i=1;i<=n;++i){ cin>>a[i]; g[a[i]].push_back(i); } for(int i=1;i<=n;++i){ int sz=g[i].size(); if(sz){ int mx=0; for(int j=1;j<sz;++j){ mx=max(mx,g[i][j]-g[i][j-1]); } mx=max(mx,g[i].front()); mx=max(mx,n-g[i].back()+1); ans[mx]=min(ans[mx],i); } } for(int i=2;i<=n;++i){ ans[i]=min(ans[i],ans[i-1]); } for(int i=1;i<=n;++i){ if(ans[i]!=1e9)cout<<ans[i]<<" "; else cout<<"-1 "; } cout<<endl; } signed main(){ int t; cin>>t; while(t--){ solve(); } }