главная новое лучшее написать

optimization


2

Ссылка на задачу — 2140. Solving Questions With Brainpower.

📋 Описание задачи

📌 Пример:

💡 Идея

Читать дальше →

ответить
3

Ссылка на задачу — 2551. Put Marbles in Bags.

📌 Описание задачи

💡 Идея

При разбиении на k подряд идущих мешков мы делаем k - 1 разрез между кусками.
Каждый разрез влияет на итоговую сумму добавлением пары вида weights[i] + weights[i+1],
где i — индекс последнего элемента в предыдущем мешке.

explanation.png

Следовательно, вся задача сводится к выбору k - 1 пар соседних кусков, которые:

Читать дальше →

ответить
2

Ссылка на задачу — 2033. Minimum Operations to Make a Uni-Value Grid.

📌 Описание задачи

Дан двумерный массив grid размером m x n, а также число x.
За одну операцию можно прибавить или

Читать дальше →

ответить
3

Ссылка на задачу — 2594. Minimum Time to Repair Cars.

❓ Описание задачи

Дано:

Нужно найти минимальное время, за которое все машины будут отремонтированы.
Предполагается, что все механики работают одновременно.

💡 Идея

Механики с меньшим рангом работают быстрее.
Произведём первичное распределение машин, используя обратный квадратный корень ранга как вес, определяющий долю машин, переданных каждому механику.

Однако это распределение не покрывает все машины. Для распределения оставшихся машин мы посчитаем для каждого механика оценку времени его работы, если взять несколько дополнительных машин (тем больше, чем больше вес механика). После остаётся лишь выбрать k-ое минимальное значение среди посчитанных времён с помощью алгоритма «QuickSelect» (любезно реализованного в стандартной библиотеке Rust).

🔍 Детали подхода

1️⃣ Быстрое распределение — вычисляем вес каждого механика и распределяем машины пропорционально.

Читать дальше →

ответить
3

Ссылка на задачу — 3480. Maximize Subarrays After Removing One Conflicting Pair.

📌 Описание задачи

Пример

💡 Идея

Читать дальше →

ответить
2

Ссылка на задачу — 2523. Closest Prime Numbers in Range.

📌 Описание задачи

Нам даны два целых числа left и right.
Нужно найти два ближайших простых числа num1 и num2 таких, что:

Если существует несколько пар с одинаковой разницей, выбрать пару с меньшим первым числом.
Если таких чисел нет, вернуть [-1, -1].

🧠 Идея

Будем просто итерироваться по парам соседних простых чисел в заданом диапазоне.
Но, так как простые близнецы (пары простых чисел, разница между которыми равна 2) встречаются довольно часто (их плотность примерно 1 / log²(n)) мы можем эффективно ввести условие раннего выхода, которое значительно улучшает среднюю производительность алгоритма.

🔍 Подход

  1. Обработка граничных случаев:
    • Если left ≤ 2 и right ≥ 3, сразу возвращаем [2, 3].
  2. Перебор чисел в диапазоне:
    • Проверяем каждое число на простоту с помощью is_prime(n), работающей за O(√n).

Читать дальше →

ответить