Метод подсчёта
Рассмотрим метод подсчёта на основе следующей задачи:
Задача
У бухгалтера есть годовой отчёт, содержащий большое количество чисел. Нужно обработать все эти данные, используя кнопочный калькулятор. Бухгалтер знает, что калькуляторы, которые продают в ближайшем магазине, не очень качественные. Он даже знает статистику по каждой кнопке: сколько нажатий она выдерживает, не ломаясь. Бухгалтер хочет узнать, сколько калькуляторов ему нужно закупить, чтобы обработать весь отчёт.
Основная идея решения этой задачи – посчитать, сколько раз встречается в отчете каждая цифра. Для подсчета можно использовать отдельные переменные cnt0
– для подсчёта нулей, cnt1
– для подсчёта единиц и т.д. Эти переменные можно объединить в единую структуру – список подсчётов из \(10\) элементов: cnt[0], cnt[1], ..., cnt[9]
, в котором индекс элемента соответствует цифре, а значение элемента – количеству раз, в котором эта цифра встречается в отчёте.
Сохраним информацию о прочности кнопки в списке press
, где press[i]
– это количество нажатий, которые выдерживает кнопка с цифрой i
.
Для получения ответа необходимо поделить каждое значение cnt[i]
на press[i]
с округлением вверх – так мы для каждого i
получим, сколько минимум калькуляторов нужно, чтобы обработать все цифры i
в отчёте. Далее, из результата для каждой цифры достаточно выбрать максимальный.
Рассмотрим пример:
cnt |
20 | 20 | 30 | 2 | 5 | 90 | 4 | 12 | 10 | 7 |
press |
5 | 1 | 3 | 4 | 10 | 12 | 40 | 50 | 10 | 2 |
ncalc |
4 |
20
|
10 | 1 | 1 | 8 | 1 | 1 | 1 | 4 |
Список ncalc
– это список, хранящий минимальное количество калькуляторов для каждой кнопки. Кнопка \(2\) требует больше всего калькуляторов – \(20\), поэтому и итоговый ответ равен двадцати. Простое и лаконичное решение получается именно из-за удобного хранения данных в списке подсчётов.
n = int(input())
a = list(map(int, input().split()))
press = list(map(int, input().split()))
cnt = [0] * 10
for ai in a:
cnt[ai] += 1
mx = float('-inf')
for i in range(10):
k = (cnt[i] + press[i] - 1) // press[i]
mx = max(mx, k)
print(f"{mx}")
Ещё одна ситуация упорядоченности, которая встречается в задачах – алфавитный или лексикографический порядок для объектов-строк.
Задача
Дана строка \(s\), состоящая из заглавных букв латинского алфавита. Найдите лексикографически наибольшую строку, полученную перестановкой символов в строке \(s\).
Поставим в соответствие каждому символу строки его ASCII
-код. Коды заглавных английских символов идут подряд от 65 до 90. Создадим список подсчетов, где будем хранить количество букв 'A'
в cnt[65]
, букв 'B'
– в cnt[66]
, ..., букв 'Z' –
в cnt[90]
. Упорядоченность индексов списка будет поддерживать и алфавитный порядок символов.
s = input()
cnt = [0] * 100
for c in s:
cnt[ord(c)] += 1
ans = ""
for i in range(90, 64, -1):
ans += chr(i) * cnt[i]
print(f"{ans}")
Метод подсчёта – эффективный и удобный способ держать под контролем элементы, для которых можно построить сравнительно небольшой список подсчётов.