C. k-Amazing Numbers(思维)

Problem - 1417C - Codeforces

 

给你一个由1到n个整数组成的数组a。

让我们把数组的k-amazing数定义为出现在数组所有长度为k的子段中的最小数字（记得长度为k的a的子段是a的连续部分，正好包含k个元素）。如果在所有长度为k的子段中没有整数出现，那么k-amazing的数字就是-1。

对于从1到n的每一个k，计算数组a的k-amazing数。

输入
第一行包含一个整数t（1≤t≤1000）--测试案例的数量。接着是t个测试用例。

每个测试用例的第一行包含一个整数n（1≤n≤3⋅105）--数组中的元素数。第二行包含n个整数a1,a2,...,an（1≤ai≤n）--数组中的元素。

保证所有测试案例的n之和不超过3⋅105。

输出
对于每个测试案例打印n个整数，其中第i个整数等于数组的第i个整数。

例子
input
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1
输出
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1 

题解:

根据题意让我们找所有长度[1,n]的字段的共有元素最小值,如果没有共有元素输出-1

我们可以转换一下题意,我们先不考虑一段的最小值,我们考虑相同的数之间相差最大的距离,

两个相同数之间的距离的最大值不就是我们要找的k吗

得到ans[距离最大值] = i

然后找相同距离最大值中最小的i不就是我们所求结果

最后对于长度大的一定覆盖长度小的子段,所以还要看一下比较一下长度大的子段最小值与长度小的字段最小值

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int a[300050];
int ans[300050];
vector<int> p[300050];
void solve()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		p[i].clear();
	}
	for(int i = 1;i <= n;i++)
	{
		ans[i] = 1e9;
		int x;
		cin >> x;
		p[x].push_back(i);
	}
	ans[0] = 1e9;
	for(int i = 1;i <= n;i++)
	{
		if(p[i].size())
		{
			int mx = 0;
			for(int j = 1;j < p[i].size();j++)
			{
				mx = max(mx,p[i][j]-p[i][j-1]);
			}
			mx = max(mx,p[i].front());
			mx = max(mx,n-p[i].back()+1);
			ans[mx] = min(ans[mx],i);
		}
	}
	for(int i = 1;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<<"\n";
}
int main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//
//