Найти минимальную стоимость перевозки груза ⇐ JAVA

[Anonymous]

У меня есть m грузовики для перевозки груза, данный грузовик доступен только в указанные дни с слева до справа, указана вместимость грузовика как Capacity и взимает некоторую сумму, представленную как Cost

Итак, у каждого грузовика есть 4 параметра: номера дней, представленные как Слева направо с мощностью и стоимостью

Для данных n дней в качестве входных данных и мне нужно перевезти груз грузоподъемностью k каждый день, найдите минимальную стоимость перевозки груза с помощью грузовиков.< /п> Пример:

n = 5 дней k = 7 производительность в день грузовики = [[1,3,5,2], [1,4,5,3], [2,5,10,1]], каждый элемент массива представляет собой левое, правое, вместимость и стоимость. Ответ:

44 Объяснение:

для грузовиков[0] = [1,3,5,2] он доступен в дни с 1 по 3, вместимость грузовика равна 5, а стоимость составляет 2. У меня есть задача нести емкость k = 7 за каждый день с количеством дней n = 5. а) День 1 День 1, у нас есть грузовики[0] и грузовики[1], но самая низкая стоимость для грузовиков[0] — 2, но вместимость — только 5. Итак, в день 1 перевезите 5 предметов с помощью грузовиков[0] и 2 предмета с помощью грузовиков[1], поэтому стоимость составит 5*2 + 2*3 = 16. б) День 2, мы можем выбрать грузовики[2]=[2,5,10,1], потому что left=2 соответствует искомому дню, а также он может перевозить 10 грузов. Стоимость второго дня составляет 7*1 = 7. в) День 3, пикаперы[2]=[2,5,10,1], поскольку 3 попадает в диапазон [2,5], стоимость дня 3 равна 7*1 = 7. г) День 4, пикапы[2]=[2,5,10,1], поскольку 4 попадает в диапазон [2,5], стоимость дня 3 равна 7*1 = 7. д) День 5, пикапы[2]=[2,5,10,1], поскольку 5 попадает в диапазон [2,5], стоимость дня 3 равна 7*1 = 7. Общая стоимость за все дни = 16+7+7+7+7 = 44. Ограничения:

Диапазон n и m от 1 до 10^4 Также у нас всегда достаточно грузовиков для перевозки груза на определенный день. Это мой код:

static longsolve(int n, int k, int[][] грузовики) { длинный результат = 0; int m = грузовики.длина; // Цикл с 1 по n дней for (int day = 1; day { вернуть p[3] - q[3]; }); // циклически перебираем все грузовики for (int j = 0; j < m; j++) { // O(m) int[] грузовик = грузовики[j]; int влево = грузовик[0], вправо = грузовик[1]; // проверяем, являются ли левые и правые допустимые диапазоны если (осталось = день) { // Добавляем очередь validTrucks.add(грузовик); } } } // находим стоимость на текущий день int dayCapacity = k; while (validTrucks.size() > 0) { // O(m) int[] грузовик = validTrucks.poll(); int вместимость = грузовик[2], TruckCost = грузовик[3]; int cap = емкость; if (dayCapacity