Задача #1692

Сортировка

Уровень ЕГЭ

(И.Карпачев) В сеть детских технопарков поступила партия новых роботов. По инструкции каждому роботу рекомендована одна батарейка с достаточной емкостью для каждого робота. Все роботы пронумерованы последовательно от 1 до N. Известно, что для каждого робота требуется ровно одна батарейка, емкость которой не меньше c_i.

Преподавателю робототехники предоставили список из M различных батареек, которые доступны для покупки. Для каждой батарейки известна ее емкость и стоимость. Необходимо определить минимальную сумму покупки батареек для всех роботов и максимальную стоимость одной батарейки, которая будет куплена при оптимальных затратах.

Входные данные:

Дан входной файл, который в первой строке содержит натуральное число N – количество новых роботов. Затем N строк содержащих целые числа c_i– минимальная емкость батарейки для робота с номером i. Затем следует натуральное число M – количество видов батареек, предоставленных для закупки. Далее в каждой из M строк содержится пара натуральных чисел a_iи b_i - емкость батарейки и ее цена соответственно.

Запишите в ответе два числа: минимальную сумму покупки батареек для всех роботов и стоимость самой дорогой батарейки, которая будет приобретена при оптимальной закупке.

Типовой пример организации файлов:

3

1

2

4

5

1 10

1 5

8 6

2 4

4 9

При таких исходных данных минимальная стоимость закупки будет составлять 14 (для первого и второго робота необходимо купить батарейки емкостью 2 и стоимостью 4, а для третьего робота емкостью 8 и стоимостью 6) 4 + 4 + 6 = 14. Цена самой дорогой купленной батарейки составит 6.

Файлы к задаче

Скачать 26.txt

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

25540

274

f = open('26.txt')
n = int(f.readline())
powers = []
for i in range(n):
    powers.append(int(f.readline()))
powers.sort(reverse=True)
m = int(f.readline())
dems = []
for _ in range(m):
    b, c = map(int, f.readline().split())
    dems.append((b, c))
dems.sort()
first, second = 0, m - 1
amount = 0
optimal = 10e20
max_price = 0
toggle = True
for first in range(n):
    while second >= 0 and powers[first] <= dems[second][0]:
        if dems[second][1] < optimal:
            optimal = dems[second][1]
        second -= 1
    if toggle:
        max_price = optimal
        toggle = False
    amount += optimal
# print(powers)
# print(dems)
print(amount, max_price)

Номер