Распределение задач* Ограничение времени 1 секунда Ограничение памяти 256 Мб Ввод стандартный ввод Вывод стандартный вывод Вася и Маша организовали производство бирдекелей. Они договорились работать день через день, при этом Вася любит простую и понятную

4 декабря 2025
Управление персоналом

#Мотивация трудовой деятельности
#Организационное поведение

Условие:

Распределение задач*
Ограничение времени 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.

Не нашел нужную задачу?Воспользуйся поиском

AI помощники

Выбери предмет

EVIEWS

SPSS

Естествознание

Ценообразование и оценка бизнеса

Черчение