А170

Постановка задачи

Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырех лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i}+a_{j}+a_{k}+a_{l}[/latex] имеет наименьшее значение.

Входные данные:

[latex]n[/latex] — количество бегунов [latex](n\geq 4)[/latex].
[latex]a_{1}, a_{2},\ldots, a_{n}[/latex] — результаты спортсменов в беге на [latex]100[/latex] м.

Выходные данные:

[latex]i, j, k, l[/latex] — номера спортсменов, избранных для команды [latex](1\leq i\leq j\leq k\leq l\leq n)[/latex]

Тесты

Входные данные Выходные данные
Количество спортсменов [latex](n)[/latex] Результаты бега спортсменов Номера спортсменов, избранных для команды
1 3 2.1  3.7  1.1 [latex]n[/latex] не должно быть меньше 4
2 4 1.4  2.1  0  0.2 Результаты должны быть больше 0
3 6 6.5  4.1  1.2  8  9.1  4.9 1  2  3  6
4 12 2.5  9  14  7.1  1.3  4.9  6.7  1.9  10.01  2.45  0.01  13 5  8  10  11

Посмотреть работу программы на примере четвертого теста можно на сайте ideone.

Решение

Описание решения

Отличительной особенностью задач из категории «потоковая обработка» является то, что обработка большого объема данных происходит циклически, без их запоминания. То есть, когда пользователь вводит в программу массив значений, программа запоминает очередное значение, обрабатывает его соответствующим образом, а потом заменяет новым поступившим значением. Это дает преимущество в использовании памяти перед программами, которые запоминают весь массив целиком.

Так как по условию размер отбираемой команды — [latex]4[/latex] бегуна ( final int teamSize = 4;), введем ограничение на количество бегунов в целом — их должно быть [latex]4[/latex] или больше, иначе программа выдаст сообщение об ошибке и завершит работу.

Введя количество бегунов n, пользователь после этого будет вводить результат каждого. Программа запоминает этот результат ровно на один шаг цикла ( double a = in.nextDouble();), за который разберется, что с ним делать, а затем заменит следующим результатом.

Так как программа не запоминает весь массив целиком, найти [latex]4[/latex] наименьших значения перебором не получится. Поэтому инициализируем [latex]2[/latex] массива, один из которых ( double[] resRun = new double[teamSize];) будет хранить результаты бегунов, отобранных в команду, а другой ( int[] nRun = new int[teamSize];) — их номера.

Результаты бегунов, отобранных в команду изначально равны нулю; это говорит о том, что еще ни один бегун в команду отобран не был. Результаты и номера первых [latex]4[/latex] бегунов мы запомним в этих массивах, так как иначе мы просто потеряем эти данные и больше не сможем сравнить их со следующими. Теперь, когда 4 бегуна отобраны, следует найти номер бегуна с наихудшим результатом (с помощью функции public static int FindMax(double[] resRun, int[] nRun)). Этот бегун — первый в очереди на замену, если очередной полученный результат вдруг окажется лучшим (меньшим). Следует отметить, что программа будет искать номер наихудшего бегуна лишь в тех случаях, когда этот бегун будет заменен; в ином случае, когда результат очередного бегуна хуже, мы замены в команде не производим, соответственно, худший бегун в команде остается тем же.

Таким образом, с каждым шагом цикла результаты отобранных в команду бегунов становятся либо меньше, либо остаются прежними. После обработки последнего введенного результата, мы получим массив resRun лучших результатов и массив nRun номеров этих бегунов. Остается лишь отсортировать номера бегунов ( Arrays.sort(nRun);), как того требует условие, и вывести их значения.

3 thoughts on “А170

  1. Программа работает. Но есть «методическое» замечание.
    Необходимость проверки корректности переданных данных обычно оговаривается в условии. В этом случае сообщается, что именно делать для некорректных данных. Чаще всего это вбрасывание исключительной ситуации указанного в задании типа.
    Если этого не требуют, то не стоит этим заниматься. Основных причин две.
    1. Бывают ситуации, когда сама задача легко решается, а проверка корректности исходных данных является сложной или вообще алгоритмически неразрешимой проблемой.
    2. Если не указано, что делать с некорректными данными, то любое действие (например, вывод сообщения в стандартный поток) может привести к тяжелым последствиям для системы в целом.
    Мораль: делаем то, что потребовали и не делаем того, чего не потребовали.
    Если очень-очень хочется сделать что-то еще, то инициируем митинг с постановщиком задачи и согласовываем изменение условий задачи. Обычно на таком митинге ничего согласовать не удается т.к. постановщик задачи тоже не глупый человек и все сформулировал как надо.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *