Решение задачи Покупка подписок на сериалы (упрощённая версия) с Codeforces

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

Единственное отличие между простой и сложной версиями — ограничения.

Канал BerTV каждый день показывает один эпизод одного из k сериалов. Вам известно расписание на ближайшие n дней: последовательность целых чисел a1,a2,…,an (1≤ai≤k), где ai — номер сериала, эпизод которого будет показан в i-й день.

Подписка на сериалы покупается целиком полностью на весь сериал, на каждый сериал подписка покупается отдельно.

Сколько минимум подписок надо купить, чтобы была возможность d (1≤d≤n) дней подряд смотреть эпизоды купленных по подписке сериалов? Иными словами, вы хотите купить минимальное количество сериалов, чтобы существовал некоторый отрезок из d подряд идущих дней, в котором все эпизоды из сериалов по приобретённым подпискам.

Код 

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k,d;
		cin>>n>>k>>d;
		map<int,int> m;
		vector<int> v(n);
		for(int i=0;i<n;i++){
			cin>>v[i];
		}
		int ans=INT_MAX;
		for(int i=0;i<d;i++){
			m[v[i]]++;
		}
		ans=min(ans,(int)m.size());
		for(int i=d;i<n;i++){
			m[v[i-d]]--;
			if(m[v[i-d]]==0){
				m.erase(v[i-d]);
			}
			m[v[i]]++;
			ans=min(ans,(int)m.size());
		}
		cout<<ans<<"\n";
	}
}

         

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




Комментарии

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


© 2020 HSECODES [email protected] Карта сайта