D
.
Size: a a a
2021 May 12
DP
по-моему любой не-направленный граф можно нарисовать в таком виде
DP
если я не прав, покажи пример графа который не подходит
D
Ну нет, не любое дерево как минимум
K
Говорю же, любой с гамильтоновым путём
D
Например 1 - 2, 2 - 3, 2 - 4, 2 - 5
D
Ну да, и как развернуть это дело в цепь?
DP
1-2-5 = цепь
D
Не, важно то, чтобы все вершины лежали на одной цепи
D
Видимо ты прав, да
D
Любой граф с гамильтоновым путем подходит
K
не надо ко мне на вы, мне неловко
ОК
похоже на плоский граф, только 3 и 5 точка должны быть соединены сверху
ОК
а, прости, хуйню спорол, так 3 и 1 соединены не плоско
М
Господа алгоритмисты, подскажите, а не проще ли решить задачу, отсортировав исходный массив по возрастанию элементов, после чего пройтись по нему с двумя указателями, подбирая для каждого предыдущего элемента последующий, который будет в 2 раза больше?
https://www.youtube.com/watch?v=3g_OeZLgK5w&t=1144s
https://www.youtube.com/watch?v=3g_OeZLgK5w&t=1144s
CD
а как ближайший выбрать?
М
0)Отсортировали массив по возрастанию;
1)Берём первый элемент, и перебираем массив поэлементно, беря первый, который будет удовлетворять условию array[i]<=2*array[j]
И так с каждым элементом
1)Берём первый элемент, и перебираем массив поэлементно, беря первый, который будет удовлетворять условию array[i]<=2*array[j]
И так с каждым элементом
CD
а почему первый был ближайшим в исходном массиве?
М
Потому что мы сперва сортируем этот массив по возрастанию элементов