Условие:
Распределение задач*
Ограничение времени 1 секунда
Ограничение памяти 256 Мб
Ввод стандартный ввод
Вывод стандартный вывод
Вася и Маша организовали производство бирдекелей. Они договорились работать день через день, при этом Вася любит простую и понятную работу, а Маша — сложную и творческую. В первый день работает Вася, во второй — Маша, потом снова Вася и т.д.
К ним поступило
N
N заказов, для каждого заказа известна его продолжительность в днях и для каждого из дней известно, будет ли в этот день работа сложной или простой. Заказы можно выполнять в любом порядке, перерывов между заказами нет.
Определите такой порядок выполнения заказов, чтобы Вася получил как можно больше простых задач, а Маша — сложных.
Формат ввода
В первой строке задается число
N
N (
1
≤
N
≤
100
000
1≤N≤100000) — количество заказов.
В следующих
N
N строках описываются заказы. Каждое описание представляет собой строку, состоящую из символов
S
S и
D
D, обозначающих, соответственно, простую и сложную работу в этот день. Длина строки не превосходит 100 символов. Суммарная длина всех строк не превосходит
1
000
000
1000000 символов.
Формат вывода
Выведите одно число — максимальное количество дней с простой работой, которые достанутся Васе.
Пример
Ввод Вывод
4
DSD
SS
DD
SDD
3
Примечания
Наибольшее количество дней с простой работой достается Васе при выполнении работ в порядке SDD, SS, DD, DSD
Решение:
Для решения задачи мы будем использовать жадный алгоритм. Основная идея заключается в том, чтобы максимизировать количество простых задач, выполняемых Васей, при этом учитывая, что он работает в нечетные дни, а Маша — в четные.
Шаг 1: Понимание задачи
Вася работает в нечетные дни (1-й, 3-й, 5-й и т.д.), а Маша — в четные (2-й, 4-й, 6-й и т.д.). Мы должны определить порядок выполнения заказов, чтобы Вася получил максимальное количество простых задач.Шаг 2: Анализ заказов
Каждый заказ имеет определенную продолжительность в днях и может быть простым (S) или сложным (D). Мы должны учитывать, что:- Заказы, которые Вася выполняет, должны содержать как можно больше S.
- Заказы, которые выполняет Маша, должны содержать как можно больше D.
Шаг 3: Сортировка заказов
Для того чтобы максимизировать количество простых задач для Васи, мы можем отсортировать заказы по количеству простых задач (S) в порядке убывания. Это позволит нам сначала выполнять заказы, которые приносят больше простых задач.Шаг 4: Выполнение заказов
После сортировки мы будем поочередно назначать заказы Васе и Маше:- Вася получает заказы в нечетные дни.
- Маша получает заказы в четные дни.
Шаг 5: Подсчет простых задач
Мы будем подсчитывать количество простых задач, которые выполняет Вася, и выводить это значение.Реализация
Теперь давайте реализуем этот алгоритм на Python.Теперь мы можем протестировать программу на примере, который был приведен в задаче. Ввод: Вывод: Таким образом, мы получили максимальное количество простых задач, которые выполняет Вася, равное 3.