Skip to content

Instantly share code, notes, and snippets.

@AnthonyMikh
Created January 7, 2018 12:50
Show Gist options
  • Save AnthonyMikh/bb86b1747f3ad8ae58cdc4364d5d52db to your computer and use it in GitHub Desktop.
Save AnthonyMikh/bb86b1747f3ad8ae58cdc4364d5d52db to your computer and use it in GitHub Desktop.
fn count_profit1(time: usize, orders: &[u32]) -> u32 {
if time == 0 || orders.len() == 0 { //микрооптимизация: если длина массива или время
return 0 //нулевое, то сразу возвращаем нуль
}
let mut sorted = orders.to_vec(); //инициализируем временный буфер
sorted.sort_unstable_by(|a, b| b.cmp(a)); //сортируем буфер по убыванию
sorted.into_iter().take(time).sum() //берём time первых элементов и суммируем
}
fn count_profit2(time: usize, orders: &[u32]) -> u32 {
use std::cmp::{min};
if time == 0 || orders.len() == 0 { //микрооптимизация: если длина массива или время
return 0 //нулевое, то сразу возвращаем нуль
}
let mut orders_list = orders.to_vec(); //инициализируем временный буфер
let mut max;
let mut max_index;
let mut sum = 0;
for _ in 0..min(time, orders.len()) { //пока есть заказы
max = 0; max_index = 0;
for (index, &value) in orders_list.iter().enumerate() { //ищем максимум
if value > max {
max = value;
max_index = index;
}
}
sum += orders_list.swap_remove(max_index); //прибавляем к аккумулятору
}
sum
}
fn main() {
assert_eq!(count_profit1(3, &[1, 1, 1, 1, 1]), 3);
assert_eq!(count_profit1(4, &[11, 2]), 13);
assert_eq!(count_profit1(4, &[8, 2, 9, 17, 4, 4, 10]), 44);
assert_eq!(count_profit2(3, &[1, 1, 1, 1, 1]), 3);
assert_eq!(count_profit2(4, &[11, 2]), 13);
assert_eq!(count_profit2(4, &[8, 2, 9, 17, 4, 4, 10]), 44);
}
@AnthonyMikh
Copy link
Author

Несколько пояснений к коду:

  1. Почему функций две? Первая — краткая и легко обозримая, но она: а) выделяет память под копию данных; б) сортирует буфер целиком. Вторая функция обходится без сортировки и вручную ищет min(time, order.len() наибольших элементов, но делает time проходов по буферу (и тоже выделяет память). В принципе, можно минимизировать потребление памяти и обойтись одним проходом по массиву, если использовать в качестве буфера лимитированный вариант пирамиды (бинарной кучи), в которой добавление нового элемента при полной заполненности приводит к удалению минимального элемента, но я слишком ленив, чтобы реализовывать этот вариант :P

  2. Почему не sort, а sort_unstable_by? Во-первых, по умолчанию сортировка производится по возрастанию, в то время как мне нужны наибольшие элементы, поэтому для удобства я сортирую по убыванию. Во-вторых, так как при решении задачи стабильность сортировки не принципиальна, я использую нестабильную сортировку как более быструю.

  3. Почему в первой функции не обрабатывается случай, когда time > orders.len()? Из-за семантики take — в случае, если элементов нужно больше, чем имеется в коллекции, итератор досрочно прерывает итерацию.

  4. Почему такая странная функция — swap_remove? Для скорости. Обычный remove будет после удаления элемента сдвигать остальные элементы справа от удалённого в памяти, т.е. имеет временную сложность O(n). swap_remove же заменяет удалённый элемент последним, поэтому работает за константное время.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment