Эта статья посвящена разбору задачи про игру в настольный теннис. Придумаем алгоритм для ее решения и напишем его на языке Java. Отмечу, что чистота кода в решении и принципы ООП принесены в жертву внятности и понятности алгоритма человеческому глазу как ни парадоксально, ведь как завещал дядя Боб чистота кода подразумевает написание исходного кода программ на человекопонятном языке. Ну да ладно, немного отошли от темы. Задача взята с одного из соревновательных раундов codeforces.com. Вашему внимание условие задачи:
К теннисному столу выстроилась очередь из n человек. Сначала первые двое играют партию в теннис. Потом проигравший встаёт в конец очереди, а победитель играет со следующим человеком из очереди, и так далее. Они играют до тех пор, пока кто-нибудь не выиграет в k партиях подряд. Этот игрок признаётся победителем.
Про каждого из участников вы знаете его силу игры в теннис, и у всех игроков они различны. В партии всегда побеждает игрок с большей силой. Определите, кто станет победителем.
В первой строке находятся два числа, разделённые пробелом: n и k (2 ≤ n ≤ 500, 2 ≤ k ≤ 1012) — количество людей и количество побед подряд, после которого игрок становится победителем, соответственно.
В следующей строке содержится n целых чисел a1, a2, …, an (1 ≤ ai ≤ n), выражающих силу игроков. Гарантируется, что эта строка содержит перестановку, то есть все ai различны.
Выведите одно число — силу победителя.
Пример:
|
1 2 |
4 2 3 1 2 4 |
|
1 |
3 |
|
1 2 3 4 5 6 7 |
Scanner l = new Scanner(System.in); // создаем объект класса сканнер, параметр - поток консоли int playersCount = l.nextInt(); // считываем первое число - количество игроков Long numberForTriumph = l.nextLong(); // считываем второе число - количество необходимых побед int[] playersPower = new int[playersCount]; // создаем массив и заполняем его элементами for (int t = 0; t < playersCount; t++) { // последовательно считывая циклом введеные через консль playersPower[t] = l.nextInt(); // параметры } |
Отлично, у нас есть входные данные! Дело за малым, осталось придумать как определить победителя. Заметим, что из условия задачи можно выделить инвариант для алгоритма: проигравший встаёт в конец очереди. Нам необязательно учитывать это условие, и описывать это условие кодом. Инвариант здесь это то, что если мы проходим до конца массива не выявив победителя, то победителем станет игрок, с наибольшей силой. Это замечание позволяет нам упростить реализацию. Напишем метод для поиска максимального элемента массива:
|
1 2 3 4 5 6 7 8 9 |
private static int getMax(int a[], int n) { int max = a[0]; for (int t = 0; t < n; t++) { if (max < a[t]) { max = a[t]; } } return max; } |
Метод статический, потому что все решение мы пишем в одном классе. Мы использовали классический прием поиска максимального элемента массива: полагаем, что максимальный элемент первый и далее сравниваем его последовательно с каждым следующим элементом массива и если максимальный меньше, то присваиваем максимуму новое значение.
Отлично, мы упростили задачу, теперь напишем функцию самого процесса игры, исходя из замеченного нами инварианта. По сути для написания нам нужно просто переписать условие задачи на язык Java.
Прежде всего обратим внимания на еще один инвариант: если нужное количество побед больше количества игроков (k>n), то победителем так же станет игрок с максимальной силой.
Мы решили половину задачи, вторая половина будет выглядеть так. Мы проводим сравнение силы игроков, до тех пор, пока кто-то из них не достигнет нужного количества побед, либо дойдем до последнего игрока. Второе условие гарантирует нам победу игрока с максимальной силой.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
private static void game(int playersCount, Long numberForTriumph, int[] playersPower) { int triumphs = 0, i = 0; // устанавливаем текущее количство побед и счетчик в 0 int activePlayerPower = playersPower[0]; // берем силу первого игрока if (numberForTriumph >= playersCount) { // проверяем условие k>n, если истино победил максимум System.out.println(getMax(playersPower, playersCount)); } else { //иначе в цикле пока не будет достигнуто нужное количество побед или конец массива while ((triumphs < numberForTriumph) && (i < playersCount - 1)) { if (activePlayerPower > playersPower[i + 1]) { // сравниваем силы игроков triumphs++; // если текущий игрок сильнее + победа i++; // двигаем счетчик } else { // иначе activePlayerPower = playersPower[i + 1]; // активный игрок теперь следующий i++; // двигаем счетчик triumphs = 1; // ставим колчиство побед для нового } // активного игрока как 1 } // ведь он победил соперника if (triumphs == numberForTriumph) { // если постигли нужного числа побед System.out.println(activePlayerPower); // выводим силу победителя } else { // иначе мы дошли до конца System.out.println(getMax(playersPower, playersCount));// победитель максимум } } } |
Алгоритм имеет сложность O(N), не самая идеальная, наверняка можно улучшить, но для нас сейчас это не важно. Вот и конечный результат, учитывающий все условия поставленной задачи. Полностью исходный код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.Scanner; public class Tennis { private static int getMax(int a[], int n) { int max = a[0]; for (int t = 0; t < n; t++) { if (max < a[t]) { max = a[t]; } } return max; } private static void game(int playersCount, Long numberForTriumph, int[] playersPower) { int triumphs = 0, i = 0; // устанавливаем текущее количство побед и счетчик в 0 int activePlayerPower = playersPower[0]; // берем силу первого игрока if (numberForTriumph >= playersCount) { // проверяем условие k>n, если истино победил максимум System.out.println(getMax(playersPower, playersCount)); } else { //иначе в цикле пока не будет достигнуто нужное количество побед или конец массива while ((triumphs < numberForTriumph) && (i < playersCount - 1)) { if (activePlayerPower > playersPower[i + 1]) { // сравниваем силы игроков triumphs++; // если текущий игрок сильнее + победа i++; // двигаем счетчик } else { // иначе activePlayerPower = playersPower[i + 1]; // активный игрок теперь следующий i++; // двигаем счетчик triumphs = 1; // ставим колчиство побед для нового } // активного игрока как 1 } // ведь он победил соперника if (triumphs == numberForTriumph) { // если постигли нужного числа побед System.out.println(activePlayerPower); // выводим силу победителя } else { // иначе мы дошли до конца System.out.println(getMax(playersPower, playersCount));// победитель максимум } } } public static void main(String[] args) { Scanner l = new Scanner(System.in); // создаем объект класса сканнер, параметр - поток консоли int playersCount = l.nextInt(); // считываем первое число - количество игроков Long numberForTriumph = l.nextLong(); // считываем второе число - количество необходимых побед int[] playersPower = new int[playersCount];// создаем массив и заполняем его элементами for (int t = 0; t < playersCount; t++) { // последовательно считывая циклом введеные через консль playersPower[t] = l.nextInt(); // параметры } game(playersCount, numberForTriumph, playersPower); } } |
2 comments On Разбор задачи про настольный теннис
Хорошая статья, продолжайте в том же духе !!!
Спасибо! Будет исполнено! Главное чтобы вам было интересно)