Задача. Даны натуральные числа [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] имеет наименьшее значение.
Тесты
| n | c | Результаты бега спортсменов | Номера спортсменов, избранных для команды | Комментарий |
| 6 | 3 | 11.77 12.34 12.14 11.15 11.16 11.40 | 4 5 6 | Пройден |
| 6 | 4 | 11.68 0 12.15 11.54 11.26 11.00 | Введен отрицательный или нулевой результат | Не пройден |
| 6 | 2 | 11.68 -12.34 12.14 11.55 11.29 11.00 | Введен отрицательный или нулевой результат | Не пройден |
Код программы на C++:
|
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 |
#include <iostream> #include <algorithm> #include <limits> using namespace std; int mini(double x[],int n) //Функция, которая возвращает номер бегуна с наилучшим результатом. { double minn = numeric_limits<double>::infinity(); int mini; for (int i = 0; i < n ; i ++)//Цикл для нахождения минимального значения. { double t = x[i]; if (t <= minn) { mini = i; minn = t; } } return mini; //Возвращение номера минимального значения } void team(double x[], int n, int c)//Функция выводящая на экран номера наилучших спортсменов. { int counters[c]; //Массив номеров бегунов. for (int i = 0; i < c ; i ++) { counters[i] = mini( x , n ); x[ counters[i] ] = numeric_limits<double>::infinity(); } sort(counters, counters + c); //Сортировка номеров бегунов for (int i = 0; i < c ; i ++) { cout<<counters[i] + 1 <<" "; } } int main() { int n, c, k = 0; //Описание переменных для хранения входных данных./ cin>>n>>c; double x[n]; //Описание массива для хранения входных данных.// for (int i = 0; i < n ; i ++) { cin>>x[i]; if (x[i] <= 0) //Проверка массива на отрицательный (либо нулевой) элемент. { cout<<"Введен отрицательный или нулевой результат"; return 0; } } team(x, n ,c); return 0; } |
В строках
|
41 42 43 44 45 46 47 48 49 |
for (int i = 0; i < n ; i ++) { cin>>x[i]; if (x[i] <= 0) //Проверка массива на отрицательный (либо нулевой) элемент. { cout<<"Введен отрицательный или нулевой результат"; return 0; } } |
мы заполняем массив элементами из входящего потока, при этом уже зная n (количество этих элементов), считав его из входящего потока заранее и проверяем на наличие отрицательного элемента либо нуля (если таковой существует, то выводим сообщение об ошибке и завершаем выполнение программы.
В конечном итоге, применяем функцию team и получаем, собственно, ответ.
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Runners { public static void main (String[] args) throws java.lang.Exception { //Описание переменных для хранения входных данных./ Scanner in = new Scanner(System.in); int n = in.nextInt(); int c = in.nextInt(); int[] counters = new int[c]; //Массив номеров бегунов. int k = 0; double[] x = new double[n]; //Описание массива для хранения входных данных.// for (int i = 0; i < n; i++) x[i] = in.nextDouble(); for (int i = 0; i < c; i++) { double minn = Double.POSITIVE_INFINITY; int mini = 0; for (int j = 0; j < n; j++) //Цикл для нахождения минимального значения. { if (x[j] <= minn) { mini = j; minn = x[j]; } } counters[i] = mini; x[counters[i]] = Double.POSITIVE_INFINITY; } Arrays.sort(counters, 0, c); //Сортировка номеров бегунов for (int i = 0; i < c ; i ++) System.out.printf(counters[i] + 1 + " "); } } |
Предлагаю подумать, как оптимально решить эту задачу при произвольном размере команды.
Подумал и дополнил.
Да, задача решится, но вряд ли решение будет оптимальным. Сложность алгоритма составляет O(c * n), что при c ~ n дает O(n^2). Существует возможность решить эту задачу за O(n).
Вы имеете в виду поразрядную сортировку? Я её только завтра расскажу на лекции
И, кстати, для c = n задача становится тривиальной — в команду входят все. Ответ 1 2 3 … n
Нет, я имею в виду k-ю порядковую статистику.
И я написал c~ n. Например, c = n / 2. Для этого случая c-я порядковая статистика — самое то.
А зачем так делать? Нам же нужно найти не k-й минимум, а k первых минимумов. Уж лучше тогда кучи если с не фиксировать. Нет?
— Не нужно вычислять размер команды случайным образом. Если уж Вы обобщили задачу (и это хорошо), то прочитайте размер команды из stdin.
— Тесты (и решение) не соответствуют условию задачи. Вы не заметили, что номера в ответе должны идти по возрастанию.
Исправил. Вопрос в следующем: Стоит ли делать сортировку кучей, что было бы рациональнее или можно оставить в таком варианте?
Сортировка кучей точно не нужна. Если сортировка, то поразрядная (цифровая). Она действительно была бы эффективней. Если использовать кучу, то только ее построение за О(n) и 4 поиска минимума (extract_min) за О(log(n)).
Но стоит ли сортировать если нужно 4 раза найти минимум? Вы так и сделали.
— Почему «номера минимального» не целое число?
— 1000.0 в 26-й строке играет роль бесконечности? Сработает конечно если это не Паралимпийские игры. Может заменить максимумом массива или привлечь константу infinyty для типа double?
— Зачем при вводе считать количество неверных данных? Причём до 1. Может лучше bool? Или сразу при нарушении напечатать сообщение об ошибке и сделать return.
Вчитался в условие.
«измеренные в сотых долях секунды»
Это скорее всего означает целое число сотых долей секунды.
Можно понять иначе — с точностью до сотых. Хоть это и не так логично.
Но Ваши тесты (11.778 12.345 12.145 11.154 11.169 11.401) не соответствуют ни первому, ни второму пониманию.
Исправил, спасибо за объяснение.
Зачтено.
Ума не приложу, почему я написал «зачтено» и не поставил оценку? Возможно из-за того, что в условии «даны натуральные числа», а в программе и тестах double.
Расширенная задача, когда требуется найти c минимумов требует некоторой коллекции из C-элементов. При реализации на Java обычно используется структура PriorityQueue (очередь с приоритетами). Вставка элемента в очередь и извлечение максимального элемента выполняется за логарифмическое время. Программа будет очень простой:
1. В цикле по i читаем элементы е из входного потока.
2. Помещаем в PriorityQueue значение i с ключом е.
3. Если в PriorityQueue стало больше чем с элементов извлекаем максимальный.
Таким образом асимптотическая сложность будет порядка [latex]O\left(n \ln c \right)[/latex], а программа займет всего несколько строк.