Постановка задачи
Даны натуральные числа [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.
Решение
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import java.util.*; class task4 { public static int FindMax(double[] resRun, int[] nRun) { double max = resRun[0]; int maxN = 0; for (int i=1; i<resRun.length; i++) { if (resRun[i] > max) { max = resRun[i]; maxN = i; } } return maxN; } public static void main (String[] args) { final int teamSize = 4; //размер отбираемой команды int n; //количество бегунов int[] nRun = new int[teamSize]; //номера бегунов double[] resRun = new double[teamSize]; //результаты этих бегунов Scanner in = new Scanner(System.in); n = in.nextInt(); if (n < teamSize) { System.out.println("n не должно быть меньше 4"); return; } double max = 0; //результат худшего бегуна в отобранной команде для сравнения с очередным результатом int maxN = 0; //номер (индекс) худшего бегуна в массиве for (int i = 0; i < n; i++) { double a = in.nextDouble(); if (a <= 0) { System.out.printf("Результаты должны быть больше 0"); return; } if (i<teamSize) //заполяем команду первыми попавшимися бегунами { nRun[i] = i; resRun[i] = a; if (i==teamSize-1) { maxN = FindMax(resRun, nRun); max = resRun[maxN]; } } else if (a < max) //заменяем бегуна с наихудшим результатом бегуном, с лучшим результатом { resRun[maxN] = a; nRun[maxN] = i; maxN = FindMax(resRun, nRun); max = resRun[maxN]; } } Arrays.sort(nRun); for (int i = 0; i<teamSize; i++) { System.out.println(nRun[i]+1); } } } |
Описание решения
Отличительной особенностью задач из категории «потоковая обработка» является то, что обработка большого объема данных происходит циклически, без их запоминания. То есть, когда пользователь вводит в программу массив значений, программа запоминает очередное значение, обрабатывает его соответствующим образом, а потом заменяет новым поступившим значением. Это дает преимущество в использовании памяти перед программами, которые запоминают весь массив целиком.
Так как по условию размер отбираемой команды — [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);), как того требует условие, и вывести их значения.
