На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый
Условие
На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы (некоторые контейнеры могут иметь одинаковую массу). Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?Входные данные.
Задание 26В первой строке входного файла находятся два числа: S — грузоподъёмность судна (натуральное число, не превышающее 100 000) и N — количество контейнеров (натуральное число, не превышающее 20 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Выходные данные.
Два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс и масса наиболее тяжёлого из них. Пример входного файла:100 480305040При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров — 30 и 40, 30 и 50 или 40 и 50. Поэтому ответ для приведённого примера: 2 50. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с оставшейся грузоподъёмностью, получим максимальное количество контейнеров, которые можно перевезти. Далее, вычитая из найденной суммы наибольшую массу контейнера в текущей последовательности, будем пробовать прибавлять контейнеры с большей массой. Если такой контейнер будет найден, то заменяем значение контейнера с наибольшей массой, который возможно поместить на судно. Приведём решение на языке Pascal.var i, j, t: integer;a: array [1..10000] of integer;s: integer;n: integer;sum: integer;maxi: integer;f: text;begin assign(f,'C:\26.txt'); reset(f); readln(f, s, n); for i := 1 to n do readln(f, a[i]); for i := 1 to n do for j := i + 1 to n do if a[i] > a[j] then begin t := a[i]; a[i] := a[j]; a[j] := t; end; sum := 0; maxi := 1; for i := 1 to n do if sum + a[i] <= s then begin sum := sum + a[i]; maxi := i; end; t := a[maxi]; for i := maxi to n do if ((sum - t) + a[i]) <= s then begin sum := sum - t + a[i]; t := a[i]; end; writeln(maxi, ' ', t);end. В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 1612
Осталось ещё 1 шаг
Примечание. Путь к файлу необходимо указать…
Бесплатно · займёт минуту