Задача
Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.
Входные данные
Первая строка: число n — количество лошадей.
Следующие n строк — в каждой указано одно целое число — характеристика соответствующей лошади.
Выходные данные
Наименьшая положительная разность характеристик.
Решение
Пусть задана конечная последовательность целых чисел a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу в лоб, нам понадобятся два цикла: один пробегает все значения по i, а другой — все значения по [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма: [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно [latex] n^2 [/latex].
Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях n лучше, чем [latex] n^2 [/latex]. Пусть b — конечная последовательность, в которой элементы последовательности a расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности b, при любом [latex] i [/latex] имеем [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых [latex] i,j [/latex] если [latex]i < j[/latex], то [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].
Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за n действий. Таким образом, новая сложность составит примерно [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно [latex] n \cdot log(n) [/latex] и, значит, для больших значений лучше «безоптимизационного» подхода.
Код на С++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { int n; // Количество лошадей cin >> n; int horses[n]; for (int i = 0; i < n; i++) { // Помещаем характеристики лошадей cin >> horses[i]; // в массив } std::sort(horses, horses + n); // Сортируем массив horses по возрастанию int min_dif = horses[1] - horses[0]; for (int i = 1; i < n - 1; i++) { // Поиск минимальной разницы характеристик int cur_dif = horses[i+1] - horses[i]; if (cur_dif < min_dif) min_dif = cur_dif; } cout << min_dif; return 0; } |
Код на Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] horses = new int[n]; for (int i = 0; i < n; i++) horses[i] = in.nextInt(); Arrays.sort(horses); int min_dif = horses[1] - horses[0]; for (int i = 1; i < n-1; i++) { int cur_dif = horses[i+1] - horses[i]; if (cur_dif < min_dif) min_dif = cur_dif; } System.out.println(min_dif); } } |
Подтверждение
Получилось! Зачёл.
Только нужно текст поправить — встречаются опечатки. Иногда забавные.
Постарался исправить опечатки. Забавную тоже пришлось устранить(
Отлично