Метка: intermediate
-
Codeforces 2161C — Loyalty (1200)
Сложность: 1200 | Теги: greedy, math, simulation Условие Вы — покупатель в магазине, который хочет купить n предметов. Цена каждого предмета i равна a[i], причем 1 ≤ a[i] ≤ X, где X — это фактор лояльности. Если после покупки предмета с ценой p ваш уровень лояльности увеличивается, вы получаете p бонусных очков. Ваша задача —…
-
Бинарное дерево поиска (BST)
Что такое BST? Бинарное дерево поиска (Binary Search Tree) — это дерево, где для каждого узла выполняется правило: все элементы в левом поддереве меньше, а в правом — больше. Пример кода на C++ Сложность Сбалансированное дерево: O(log n) для поиска, вставки, удаления Дегенерированное (как связный список): O(n) std::set и std::map в C++ STL используют сбалансированные…
-
Динамическое программирование: задача о рюкзаке
Что такое динамическое программирование? Динамическое программирование (DP) — метод решения задач, которые можно разбить на перекрывающиеся подзадачи. Решения подзадач кэшируются, чтобы не пересчитывать их повторно. Пример кода на C++ Сложность Время: O(n × W) Память: O(n × W) Когда использовать? DP идеально подходит для задач оптимизации, где нужно найти максимальное или минимальное значение при определённых…
-
Быстрая сортировка QuickSort
Что такое быстрая сортировка? Быстрая сортировка (QuickSort) — один из самых эффективных алгоритмов сортировки, использующий принцип «разделяй и властвуй». Алгоритм выбирает «опорный элемент» (pivot), разделяет массив на две части (меньше и больше опорного) и рекурсивно сортирует каждую часть. Пример кода на C++ Сложность Худший случай: O(n²) — массив уже отсортирован (при плохом выборе pivot) Средний…