Решение задачи "Настольный теннис" с Codeforces

С пояснением   Просмотров: 17


К теннисному столу выстроилась очередь из n человек. Сначала первые двое играют партию в теннис. Потом проигравший встаёт в конец очереди, а победитель играет со следующим человеком из очереди, и так далее. Они играют до тех пор, пока кто-нибудь не выиграет в k партиях подряд. Этот игрок признаётся победителем.

Про каждого из участников вы знаете его силу игры в теннис, и у всех игроков они различны. В партии всегда побеждает игрок с большей силой. Определите, кто станет победителем.

Код

#include<iostream>
using namespace std;
long long n,m,k,x,y,i;
main(){
	cin>>n>>k>>x;
	for(i=1;i<n;i++){
		cin>>y;
		if(m == k)break;
		if(x > y)m++;
		else{
			x=y;
			m=1;
		}
	}
	cout<<x<<endl;
}

         

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


Не очень сложно решить эту задачу за O(k + n). Условие даже подсказывает, что для этого подходит структура данных очередь. Для этого нужно поддерживать очередь участников, текущего победителя и количество побед у него. Каждая партия обрабатывается за O(1). Можно доказать, что число партий не превосходит n + k.

Конечно, такое решение слишком медленное. Давайте подумаем, что будет происходить при большом k. Точнее, пусть k ≥ n - 1. Чтобы стать победителем, нужно одержать не менее n - 1 побед подряд, то есть нужно выиграть у всех остальных игроков. Значит, победителем станет игрок с максимальной силой.

Таким образом, если k ≥ n - 1, мы умеем решать задачу за O(1), а иначе можно запустить симуляцию, описанную в начале, и она будет работать за O(n).

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

Комментарии

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