Ссылка на задачу – 3066. Minimum Operations to Exceed Threshold Value II.
📝 Описание задачи
Дан массив nums и число k. Мы можем выполнять следующую операцию, пока в массиве есть хотя бы два элемента:
- Взять два наименьших числа
x и y.
- Удалить их из массива.
- Добавить новое число
2·min(x,y) + max(x,y).
Необходимо найти количество операций, чтобы все числа в массиве стали ≥ k.
💡 Идея
Мы объединяем два наименьших числа, поэтому важно быстро находить и извлекать их.
Для этого можно использовать очередь с приоритетами (BinaryHeap), но в нашем случае можно действовать эффективнее.
🔹 Заведём две очереди (VecDeque):
orig_values — содержит исходные числа < k, отсортированные по возрастанию.new_values — хранит новые числа, появляющиеся в процессе операций, в гарантированно возрастающем порядке.
Благодаря двум упорядоченным очередям, минимальные элементы можно извлекать за O(1), а вся процедура будет работать эффективнее, чем с BinaryHeap.
🔍 Детали подхода
- Отфильтровываем числа
< k и сортируем их (orig_values).
- Используем две очереди
(VecDeque), чтобы извлекать минимальные элементы за O(1).
- В цикле, пока в объединённых очередях больше одного элемента:
- Извлекаем два наименьших числа из
orig_values или new_values.
- Создаём новый элемент
2 * min + max.
- Если он всё ещё
< k, добавляем его в new_values.
- Увеличиваем счётчик операций.
- Когда остаётся ноль или один элемент, возвращаем число операций, учитывая возможную последнюю операцию для удаления оставшегося элемента.
📊 Асимптотика
-
Временная сложность:
O(n·log n)
- Сортировка
orig_values занимает O(n·log n).
- Каждое извлечение и добавление выполняется за
O(1) благодаря VecDeque.
- Всего
O(n) операций объединения, что c учётом предварительной сортировки даёт общую сложность O(n·log n).
-
Дополнительная память:
O(n)
- Используем два
VecDeque, которые в сумме хранят не более n элементов.
💻 Исходный код
use std::collections::VecDeque;
impl Solution {
pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
// Collect numbers less than k and store them in a VecDeque for efficient front access
let mut orig_values: VecDeque<i32> = nums.into_iter()
.filter(|&n| n < k)
.collect();
orig_values.make_contiguous().sort_unstable(); // Sort original values
let mut new_values: VecDeque<i32> = VecDeque::new(); // Stores newly generated values
let mut ops = 0;
// Process elements until only one remains
while orig_values.len() + new_values.len() > 1 {
let e1 = Self::pick_smallest(&mut orig_values, &mut new_values).unwrap() as i64;
let e2 = Self::pick_smallest(&mut orig_values, &mut new_values).unwrap() as i64;
// Merge two smallest values
let new_val = 2 * e1 + e2;
if new_val < k as i64 {
new_values.push_back(new_val as i32); // Insert new value in sorted order
}
ops += 1;
}
// Return total operations including any remaining elements
(ops + orig_values.len() + new_values.len()) as i32
}
/// Picks and removes the smallest element from either `orig_values` or `new_values`.
fn pick_smallest(orig_values: &mut VecDeque<i32>, new_values: &mut VecDeque<i32>) -> Option<i32> {
match (orig_values.front(), new_values.front()) {
(None, None) => None,
(Some(_), None) => orig_values.pop_front(), // Take from orig_values if new_values is empty
(Some(x), Some(y)) if x <= y => orig_values.pop_front(), // Take from orig_values if it's smaller
_ => new_values.pop_front(), // Otherwise, take from new_values
}
}
}
Tags: #rust #algorithms #simulation