92. Подпроекты

Рамзи Сарнаех создал новую компанию пригородных услуг, которую назвал Нерешенные Идеи (НИ). Пока Рамзи в НИ еще не нанял работников, поэтому он первые несколько месяцев должен работать сам, пока он не сможет расширить свою компанию. Недавно он получил некоторые проекты от правительственных министерств и разбил все проекты на меньшие независимые подпроекты с разными стоимостями. Мы предполагаем, что все подпроекты могут быть выполнены за единицу времени. Рамзи, имея ограниченное время, но будучи оптимистом, хочет знать, сколько, в наилучшем случае, он может заработать, принимая более ценные подпроекты и отклоняя другие.

Вход. Первая строка содержит количество тестов. Каждый тест задается одной строкой и начинается с двух целых чисел: времени t, имеющегося в распоряжении Рамзи и количество подпроектов p соответственно (0 ≤ t, p ≤ 1000). За этими двумя числами следует p неотрицательных целых чисел (от 0 до 32767, включительно), которые являются значениями стоимости подпроектов.

Выход. Для каждого теста вывести в одной строке максимальную заработанную сумму денег (сумму значений), которую можно достичь в пределах доступного времени Рамзи.

Пример входа	Пример выхода
3 3 5 1 1 1 1 1 4 2 161 5 4 7 8 2 9 17 4 4 10	3 166 44

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Очевидно, что Рамзи выгодней выполнять подпроекты с наиболее высокой стоимостью. Отсортируем стоимости подпроектов и найдем сумму стоимостей t наиболее ценных из них. Если t ≥ p, то следует выполнить все подпроекты.

Пример

Во втором примере все 2 проекта можно выполнить за 4 единицы времени. Заработок составит 161 + 5 = 166.

В третьем примере из 7 проектов следует выбрать 4 самых ценных. Отсортируем стоимости подпроектов:

Стоимость четырех самых ценных из них равна 8 + 9 + 10 + 17 = 44.

Реализация алгоритма

Читаем входные данные. Стоимости подпроектов сохраняем в массиве m.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&t,&p);

for(i = 0; i < p; i++)

scanf("%d",&m[i]);

Сортируем стоимости подпроектов по возрастанию.

sort(m, m + p);

В переменной s находим сумму стоимостей t самых ценных подпроектов. Если t ≥ p, то находим сумму стоимостей всех подпроектов.

s = 0;

for(i = p - 1; i >= max(p - t, 0); i--)

s += m[i];

Выводим ответ.

printf("%d\n",s);

}

Python реализация

Читаем входные данные. Стоимости подпроектов сохраняем в списке m.

tests = int(input())

for _ in range(tests):

t, p, *m = map(int, input().split())

Сортируем стоимости подпроектов по возрастанию.

m.sort()

В переменной s находим сумму стоимостей t самых ценных подпроектов. Если t ≥ p, то находим сумму стоимостей всех подпроектов.

s = 0

for i in range(p - 1, max(p - t - 1, -1), -1):

s += m[i]

Выводим ответ.

print(s)