MiddleКодИногдаЕщё не отвечали
Разбить массив на 3 части с минимальной суммой стоимостей первых элементов
Массив длины n (n >= 3) надо разбить на 3 непрерывные непустые части. Стоимость части — её первый элемент. Верните минимальную возможную суммарную стоимость. [1,2,3,12] → 6 (части [1],[2],[3,12]).
Требования:
- O(n) за один проход; сортировка запрещена.
int minSplitCost(const std::vector<int>& nums) {
// ваш код здесь
}Допишите реализацию.
Первая часть всегда начинается с индекса 0, поэтому её стоимость фиксирована как nums[0]. Две другие части начинаются с любых двух индексов > 0, поэтому их стоимости — два наименьших среди nums[1..]. Ответ — nums[0] плюс эти два минимума, за один O(n) проход.
- ✗Сортировать и не заметить, что стоимость первой части вынужденно равна nums[0]
- ✗Включать nums[0] при поиске двух минимумов остальных частей
- ✗Использовать двойной цикл за O(n²), когда достаточно одного прохода
- →Почему стоимость первой части вынуждена, а остальные свободны быть любыми двумя поздними индексами?
- →Как изменится ответ при разбиении на k частей?
Оглавление
Задача
Разбейте массив на 3 части с минимальной суммой стоимостей первых элементов, за O(n).
Решение
#include <vector>
#include <algorithm>
#include <climits>
int minSplitCost(const std::vector<int>& nums) {
int min1 = INT_MAX, min2 = INT_MAX;
for (size_t i = 1; i < nums.size(); ++i) { // только nums[1..]
if (nums[i] < min1) { min2 = min1; min1 = nums[i]; }
else if (nums[i] < min2) { min2 = nums[i]; }
}
return nums[0] + min1 + min2;
}Ключевые моменты
- Первая часть фиксирована: её стоимость
nums[0]. - Две другие части дают два наименьших значения из
nums[1..]. - Один проход, без сортировки — отслеживаем два минимума.
Оглавление
