Question

В морском порту готовятся к перевозке грузов разной массы и формы, для этого каждый груз помещают в отдельный контейнер. Контейнеры имеют разную грузоподъемность (некоторые контейнеры могут иметь одинаковую грузоподъёмность). Из-за компьютерного сбоя из общего количества контейнеров для перевозки выделили первые попавшиеся контейнеры. Напишите программу, которая поможет посчитать максимальное количество грузов, которое можно отправить в выделенных контейнерах, и максимальную массу одного отправленного груза.*Формат входных данных:*В первой строке входного файла находится число *N* — количество грузов, совпадающее с выделенным количеством контейнеров (натуральное число, не превышающее 20 000). Каждая из следующих *N* строк содержит два натуральных числа, не превышающих 100 000: массу груза и максимальную грузоподъёмность контейнера.*Формат выходных данных:*Два целых неотрицательных числа: максимальное количество грузов, которое можно отправить в выделенных контейнерах и максимальную массу одного отправленного груза.**Входные данные.**Задание 26

В первой строке входного файла находится число *N* — количество грузов и количество контейнеров на складе (натуральное число, не превышающее 20 000). Каждая из следующих *N* строк содержит два натуральных числа, не превышающих 100 000: массу груза и максимальную массу груза, который можно поместить в контейнер.Выходные данныеДва целых неотрицательных числа: максимальное число грузов и максимальную массу груза.**Типовой пример организации входных данных:**710 5020 6070 2040 2050 1010 1020 15Для приведённого примера ответом является пара чисел: 6; 50.*Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.*

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

В морском порту готовятся к перевозке грузов разной массы. Каждый груз помещают в отдельный контейнер. Контейнеры имеют разную грузоподъёмность. Из-за сбоя выделили первые попавшиеся контейнеры.

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

**Формат входных данных:**

В первой строке — число $N$ (количество грузов и контейнеров, $N \leq 20\,000$). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100\,000$: массу груза и максимальную грузоподъёмность контейнера.

**Формат выходных данных:**

Два целых числа: максимальное количество грузов и максимальную массу одного отправленного груза.

**Пример:**

Входные данные:
```
7
10 50
20 60
70 20
40 20
50 10
10 10
20 15
```

Выходные данные:
```
6 50
```

### РЕШЕНИЕ

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

Алгоритм:
1. Прочитать данные: массы грузов и грузоподъёмности контейнеров.
2. Отсортировать оба массива в порядке убывания.
3. Применить двухуказательный метод: для каждого контейнера (начиная с самого вместительного) найти самый тяжёлый груз, который в него поместится.
4. Если груз помещается — добавить его в список отправленных и перейти к следующему контейнеру. Если нет — перейти к более лёгкому грузу.
5. Вывести количество отправленных грузов и максимальную массу среди них.

```python
gk = [list(map(int, s.split())) 
      for s in open('26_59822.txt')][1:]

g = sorted(x[0] for x in gk)  # грузы
k = sorted(x[1] for x in gk)  # контейнеры
p = []  # отправленные грузы

while g and k:
    while g and g[-1] > k[-1]:
        g.pop()
    if g:
        p.append(g.pop())
        k.pop()

print(len(p), max(p))
```

Сложность: $O(n \log n)$ (доминирует сортировка).

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике