Вопрос или проблема
У меня есть транспортное средство, которое имеет максимальную вместимость для перевозки предметов за одну поездку, и в каждой поездке оно может забрать максимальное количество предметов одного типа.
Пример: У меня есть массив предметов, где items[i] указывает количество предметов типа i.
items = [4,4,3]
вместимость транспортного средства за одну поездку = 3
максимальное количество предметов одного типа, разрешенное за одну поездку, составляет 3
вывод: 3
Ограничения:
n — размер массива предметов, 1 <= n <= 10^5
1 <= items[i] <= 10^5
1 <= вместимость <= 10^5
1 <= max_allowed_same_type <= 10^5
Вот мой код:
public static long solve(List<Integer> items, int capacity, int max_allowed_same_type) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.addAll(items);
long result = 0;
while (!pq.isEmpty()) {
int load = 0;
while (load < capacity && !pq.isEmpty()) {
int item = pq.poll();
int minItem = Math.min(max_allowed_same_type, item);
int e = load + minItem;
if (e > capacity) {
int diff = capacity - load;
pq.add(item - diff);
break;
} else {
load += minItem;
}
if (item > minItem) {
pq.add(item - minItem);
}
}
result++;
}
return result;
}
public static void main(String[] args) {
// Тест 1
System.out.println(solve(Arrays.asList(4, 4, 3), 3, 3)); // 4
// Тест 2
System.out.println(solve(Arrays.asList(3, 2, 2, 6), 2, 1)); // 7
// Тест 3 (тот, который не проходил)
System.out.println(solve(Arrays.asList(1, 4), 1, 2)); // 5
}
Я не уверен, какова будет временная сложность этого кода. Я предполагаю, что временная сложность моего кода составляет O(sum(items)) в худшем случае, поправьте меня, если я ошибаюсь. Каков правильный подход для решения этой проблемы с меньшей временной сложностью.
Вы используете PriorityQueue, чтобы получить максимальный элемент на каждой итерации цикла. Это добавляет логарифмическую составляющую к вашей сложности, где n — размер кучи. Таким образом, сложность вашего алгоритма должна составлять O(s*log(n)), где s=sum(items). Однако, на мой взгляд, нет смысла использовать кучу. Вы можете просто пройтись по массиву предметов, уменьшая значение каждого предмета не более чем на max_items, чтобы получить общий вес нагрузки до вместимости.
Ответ или решение
Чтобы минимизировать количество поездок, необходимых для перевозки предметов, необходимо оптимально распределить загрузку транспортного средства с учетом его ограничений. Рассмотрим более эффективный способ решения этой задачи, который не требует использования очереди с приоритетом, и имеет меньшую временную сложность.
Анализ вашей текущей реализации
Вы используете очередь с приоритетом для получения максимального количества предметов на каждом шаге, что вносит дополнительную сложность в ваш код. Применяемый алгоритм фактически имеет временную сложность O(s * log(n)), где s — сумма всех предметов, а n — количество видов предметов.
Оптимизированный подход
Для решения задачи мы можем воспользоваться простым циклом для перебора различных типов предметов, принимая во внимание как максимальную вместимость автомобиля, так и максимальное количество предметов одного типа, которое можно загрузить за одну поездку.
- Рассмотрим каждый тип предмета.
- Загрузим максимальное количество предметов этого типа, учитывая ограничения.
- Продолжим до тех пор, пока все предметы не будут перевезены.
Этот подход можно реализовать с временной сложностью O(n), так как мы просто проходим по массиву предметов и выполняем арифметические операции.
Пример реализации
Вот упрощенная версия вашего кода на Java:
public static long solve(List<Integer> items, int capacity, int max_allowed_same_type) {
long trips = 0; // количество поездок
for (int item : items) {
while (item > 0) {
trips++; // каждая итерация это поездка
int load = 0; // текущая загрузка
// Загружаем предметы данного типа, не превышая ограничения
while (load < capacity && item > 0) {
int toLoad = Math.min(max_allowed_same_type, item); // максимально допустимое количество для загрузки
if (load + toLoad <= capacity) {
load += toLoad; // обновляем загрузку
item -= toLoad; // уменьшаем количество предметов данного типа
} else {
int diff = capacity - load; // оставшееся свободное место
item -= diff; // корректируем количество оставшихся предметов
break; // при достижении полной загрузки выходим из цикла
}
}
}
}
return trips;
}
public static void main(String[] args) {
// Тестовые случаи
System.out.println(solve(Arrays.asList(4, 4, 3), 3, 3)); // Ожидаемый вывод: 3
System.out.println(solve(Arrays.asList(3, 2, 2, 6), 2, 1)); // Ожидаемый вывод: 7
System.out.println(solve(Arrays.asList(1, 4), 1, 2)); // Ожидаемый вывод: 5
}Вывод
Срезая использование очереди с приоритетом и вместо этого просто проходя по массиву предметов с учетом их количества и ограничений, вы можете значительно улучшить временную сложность вашего алгоритма. Теперь он работает с временной сложностью O(n), что делает его более эффективным для больших входных данных.
Таким образом, вместо O(s * log(n)), как в вашей первоначальной реализации, мы добились временной сложности O(n), что является идеальным решением для данной задачи.