Решение задачи "Задоминированный подмассив" с Codeforces

Без пояснения   Просмотров: 14

Назовем массив t задоминированным значением v в следующем случае.

Во-первых, массив t должен состоять хотя бы из 2 элементов. Теперь, давайте посчитаем количество вхождений каждого числа num в t и назовем данное значение occ(num). Тогда, t — задоминирована (числом v) тогда (и только тогда), когда occ(v)>occ(v′) для любого другого числа v′. Например, массивы [1,2,3,4,5,2], [11,11] и [3,2,3,2,3] задоминированы (числами 2, 11 и 3 соответственно), но массивы [3], [1,2] и [3,3,2,2,1] — нет.

Небольшая заметка: так как любой массив может быть задоминирован только одним числом, то мы можем не уточнять данное число и просто говорить, что массив либо задоминирован, либо нет.

Вам задан массив a1,a2,…,an. Определите его самый короткий задоминированный подмассив, либо скажите, что таких нет.

Подмассив массива a — это последовательная часть массива a, другими словами массив ai,ai+1,…,aj для некоторых 1≤i≤j≤n.

Код 

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> a(n+1);
		int k,r,ans=1e9;
		for(int i=1;i<=n;i++)
		{
			cin>>k;
			if(a[k])
				ans=min(ans,i-a[k]+1);
			a[k]=i;
		}
		cout<<(ans<1e9?ans:-1)<<'\n';
	}
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться