Ссылка на задачу — 2551. Put Marbles in Bags.
📌 Описание задачи
- Дан массив
weights, где weights[i] — вес i-го куска мрамора.
- Требуется разделить все куски на
k непустых мешков, соблюдая следующие правила:
- Каждый мешок содержит хотя бы один кусок.
- Если в мешке есть куски с индексами
i и j, то все элементы между ними также должны входить в этот мешок.
- Стоимость мешка — это сумма весов первого и последнего куска в нём, то есть:
weights[i] + weights[j].
- Нужно вернуть разность между максимально возможной и минимально возможной общей стоимостью всех
k мешков.
💡 Идея
При разбиении на k подряд идущих мешков мы делаем k - 1 разрез между кусками.
Каждый разрез влияет на итоговую сумму добавлением пары вида weights[i] + weights[i+1],
где i — индекс последнего элемента в предыдущем мешке.
Следовательно, вся задача сводится к выбору k - 1 пар соседних кусков, которые:
- минимизируют сумму (для минимального варианта),
- максимизируют сумму (для максимального варианта).
Читать дальше →
ответить
Ссылка на задачу — 2140. Solving Questions With Brainpower.
📋 Описание задачи
- Дан вектор
questions (questions[i] = [pointsi, brainpoweri]).
- Вы проходите тест, состоящий из последовательности вопросов.
- Если вы решаете вопрос
i, то зарабатываете pointsi баллов, но пропускаете следующие brainpoweri вопросов.
- Вопросы можно пропускать
- Нужно определить, максимальное количество баллов, которое можно набрать, действуя оптимально.
📌 Пример:
- Вход:
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
- Размышления:
- Если решить вопрос
0, вы получите 3 очка и пропустите вопросы 1 и 2, перейдёте сразу к 3 → итого: 3 + 2 = 5.
- Если пропустить
0 и решить 1, вы получите 4 очка и пропустите 2 и 3 → итого: 4.
- Если пропустить
0 и 1, решить 2 → получите 4 очка, но пропустите 3 → итого: 4.
- Если пропустить
0–2 и решить 3 → получите 2 очка.
🔎 Оптимальная стратегия: решить вопросы 0 и 3, что даст нам 5 баллов на экзамене.
- 👉 Ответ:
5.
💡 Идея
Читать дальше →
ответить
Ссылка на задачу — 2033. Minimum Operations to Make a Uni-Value Grid.
📌 Описание задачи
Дан двумерный массив grid размером m x n, а также число x.
За одну операцию можно прибавить или
Читать дальше →
ответить
Ссылка на задачу — 2594. Minimum Time to Repair Cars.
❓ Описание задачи
Дано:
ranks — список рангов механиков.- механик с рангом
r может починить n машин за r * n² минут.
cars — общее количество машин, ожидающих ремонта.
Нужно найти минимальное время, за которое все машины будут отремонтированы.
Предполагается, что все механики работают одновременно.
💡 Идея
Механики с меньшим рангом работают быстрее.
Произведём первичное распределение машин, используя обратный квадратный корень ранга как вес, определяющий долю машин, переданных каждому механику.
Однако это распределение не покрывает все машины. Для распределения оставшихся машин мы посчитаем для каждого механика оценку времени его работы, если взять несколько дополнительных машин (тем больше, чем больше вес механика). После остаётся лишь выбрать k-ое минимальное значение среди посчитанных времён с помощью алгоритма «QuickSelect» (любезно реализованного в стандартной библиотеке Rust).
🔍 Детали подхода
1️⃣ Быстрое распределение — вычисляем вес каждого механика и распределяем машины пропорционально.
Читать дальше →
ответить
Ссылка на задачу — 3480. Maximize Subarrays After Removing One Conflicting Pair.
📌 Описание задачи
- Дан массив чисел от
1 до n и список конфликтных пар conflicting_pairs,
где каждая пара [a, b] запрещает подотрезки[1, n] , в которых a и b встречаются совместно.
- Требуется удалить ровно одну конфликтную пару так,
чтобы получить максимальное количество подотрезков из [1, n], удовлетворяющих оставшимся ограничениям.
Пример
- Входные параметры:
n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
- Ответ:
12
- Объяснение:
Удаляем [1, 2] из массива конфликтных пар. Остаются: [[2, 5], [3, 5]].
Всего 12 подотрезков удовлетворяют условию не содержать одновременно 2 и 5 или 3 и 5.
Это отрезки: 1..1, 1..2, 1..3, 1..4, 2..2, 2..3, 2..4, 3..3, 3..4, 4..4, 4..5, 5..5
💡 Идея
- Ключевое наблюдение заключается в том, что конфликтные пары создают ограничения на диапазоны, ограничивая допустимые подотрезки.
Читать дальше →
ответить
Ссылка на задачу — 2523. Closest Prime Numbers in Range.
📌 Описание задачи
Нам даны два целых числа left и right.
Нужно найти два ближайших простых числа num1 и num2 таких, что:
left ≤ num1 < num2 ≤ right- Оба числа простые
- Разница
num2 - num1 минимальна среди всех возможных пар
Если существует несколько пар с одинаковой разницей, выбрать пару с меньшим первым числом.
Если таких чисел нет, вернуть [-1, -1].
🧠 Идея
Будем просто итерироваться по парам соседних простых чисел в заданом диапазоне.
Но, так как простые близнецы (пары простых чисел, разница между которыми равна 2) встречаются довольно часто (их плотность примерно 1 / log²(n)) мы можем эффективно ввести условие раннего выхода, которое значительно улучшает среднюю производительность алгоритма.
🔍 Подход
- Обработка граничных случаев:
- Если
left ≤ 2 и right ≥ 3, сразу возвращаем [2, 3].
- Перебор чисел в диапазоне:
- Проверяем каждое число на простоту с помощью
is_prime(n), работающей за O(√n).
Читать дальше →
ответить
