C. k-Amazing Numbers
题意
给出一个长度为n<1e5的数组a (0<ai<=n)
对于每个长度为k的子区间都存在的最小的数为ans[i]
输出k从1到n对应的ans[i]
题解
对于”求每个长度为k的子区间都存在的最小的数”不好直接处理
不妨先考虑相同数之间最少需要多长的k才能都包含到
因为对于一个数A它成为所有长度为k的子区间都存在的数 一定要满足
任意一个区间都有A 那么就要求对应区间长度k>=max(相邻两个A的间隔)
所有长度为k+1的子区间都存在的最小的数=min(所有长度为k+1的子区间都存在的数,对于所有长度为k的子区间都存在的最小的数)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e5+5;
const ll Mod=998857459;
int data[Max],ans[Max];
vector<int>pos[Max];
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=1;i<=n;i++)ans[i]=1e9,pos[i].clear();
for(int i=1;i<=n;i++){
cin>>data[i];
pos[data[i]].push_back(i);
}
for(int i=1;i<=n;i++){
if(pos[i].empty())continue;
int dis=max(pos[i].front(),n-pos[i].back()+1);
for(int j=1;j<pos[i].size();j++)dis=max(dis,pos[i][j]-pos[i][j-1]);
ans[dis]=min(ans[dis],i);
}
for(int i=2;i<=n;i++)ans[i]=min(ans[i-1],ans[i]);
for(int i=1;i<=n;i++){
if(ans[i]==1e9)cout<<-1<<" ";
else cout<<ans[i]<<" ";
}
cout<<endl;
}
}
|