思路
對于每個數，考慮相同數之間最少需要多長的k才能將其涵蓋，列舉一個數與序列開頭、中間數之間的差和序列結尾，程序中記錄長度k范圍內最小的數值，
代碼
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define pb push_back
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int minn=0xc0c0c0c0;
vector<int>s[maxn];
int n,t,x,a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<=n;i++)
{
a[i]=inf;
s[i].clear();
}
for(int i=1;i<=n;i++)
{
cin>>x;
s[x].pb(i);//x出現的位置
}
for(int i=1;i<=n;i++)
{
if(!s[i].empty())
{
int tmp=0;
for(int j=1;j<s[i].size();j++)
tmp=max(tmp,s[i][j]-s[i][j-1]);//i出現的相鄰位置的最大間距
tmp=max(tmp,s[i].front());
tmp=max(tmp,n-s[i].back()+1);
a[tmp]=min(a[tmp],i);//至多tmp的長度覆寫的范圍中最小的數字
}
}
for(int i=2;i<=n;i++)
a[i]=min(a[i],a[i-1]);//更新前綴和，小區間可覆寫的大區間一定可以
for(int i=1;i<=n;i++)
{
if(a[i]!=inf)
cout<<a[i]<<" ";
else
cout<<"-1"<<" ";
}
cout<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/152796.html
標籤：其他
上一篇：【rosbridge】ROS與Android通信（配置編譯 apk 檔案）
下一篇：JAVASCRIPT知識點（一）