В следующих N строках находятся значения объёмов файлов каждого
Условие
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей. Входные данные.
Задание 26В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 2000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:100 480305040При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов — 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:2 50 Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с размером свободного места на диске, получим максимальное количество пользователей, чьи файлы могут поместиться на диске. Далее, вычитая из найденной суммы наибольший файл в текущей последовательности, будем пробовать прибавлять файлы с большим весом. Если такой файл будет найден, то заменяем значение наибольшего файла, который возможно поместить на диск. Приведём решение на языке Pascal.var i, j, t: integer;a: array [1..2000] of integer;s: integer;n: integer;sum: integer;maxi: integer;f: text;begin assign(f,'C:\27886.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.
Осталось ещё 1 шаг
Примечание. Путь к файлу необходимо указать…
Бесплатно · займёт минуту