Решение задачи Социальная сеть (простая версия) с Codeforces

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


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

Вы общаетесь в одной из популярных социальных сетей, используя свой смартфон. Ваш смартфон может показывать не более k самых недавних бесед с вашими друзьями. Изначально экран смартфона пуст (то есть количество показанных бесед равно 0).

Каждая беседа — это ваш диалог с каким-то из ваших друзей. Всего существует не более одной беседы с каждым из ваших друзей. Таким образом, каждая беседа однозначно определяется вашим другом.

Вы (внезапно!) обладаете возможностью видеть будущее. Вы знаете, что в течение дня вы получите n сообщений, i-е сообщение будет получено от друга с ID idi (1≤idi≤109).

Если вы получаете сообщение от друга idi тогда, когда беседа с ним сейчас показана на экране смартфона, то ничего не происходит: беседы на экране не меняются и не меняют свой относительный порядок, вы просто читаете сообщение и продолжаете ждать новых сообщений.

Иначе (то есть тогда, когда на экране нет беседы с другом idi):

Сначала, если количество бесед, отображенных на экране, равно k, последняя беседа (которая имеет позицию k) удаляется с экрана.
Теперь количество бесед на экране гарантированно меньше k и беседа с другом idi не отображена на экране.
Беседа с другом idi появляется на первой (верхней) позиции на экране и все другие отображенные беседы сдвигаются на одну позицию вниз.
Ваша задача — найти список бесед (в порядке, в котором они будут отображены на экране) после обработки всех n сообщений.

Код

#include <bits/stdc++.h>
using namespace std;

int main()
{
	long long n,k,id;
	cin>>n>>k;
	vector<long long> v;
	while(n--){
		cin>>id;
		if(find(v.begin(),v.end(),id) == v.end()){
			if(v.size() >= k) v.pop_back();
			v.emplace(v.begin(),id);
		}
	}
	cout<<v.size()<<endl;
	for(auto i : v){
		cout<<i<<" ";
	}
	return 0;
}

         

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



Комментарии

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