Опытная команда
Каждому тимлиду важно следить за опытностью своей команды. А именно выделять самого опытного члена своей команды и понимать, как его опытность соотносится с опытностью остальных членов его команды
Команда - это живой организм, ее состав постоянно изменяется. Иногда к ней присоединяются новые инженеры, порой кто-то уходит. Бывает, что кто-то возвращается в команду после ухода и даже проделывает это несколько раз!
Дан список пар <имя, момент времени>, упорядоченный по неубыванию времени и описывающий события, происходящие с командой. Изначально состав команды пустой. Если на текущий момент в команде не содержится инженера с таким именем, то событие означает, что он в заданный момент времени присоединяется к команде. Иначе, что он наоборот уходит из команды
Опытность - это суммарное количество времени, которое конкретный инженер провел в команде. Более формально, опытность - это сумма разностей между текущим моментом (или моментом ухода) и соответствующим ему моментом присоединения к команде по всем периодам работы инженера в команде.
После обработки каждого события требуется определить самого опытного члена команда и то, насколько суммарная опытность оставшейся части команды (то есть всех, кроме самого опытного) больше опытности самого опытного члена команды
Формат ввода
На первой строке дано единственное число N (1≤N≤300 000) - количество событий
Далее в каждой из N строк через пробел заданы два параметра S и T
S - имя члена команды (состоит из строчных и прописных латинских букв, 1≤∣S∣≤10)
T - момент времени (1≤T≤1 000 000 000)
Все события упорядочены по неубыванию времени. Иными словами, гарантируется, что для любых i<j справедливо Ti≤Tj
Все события уникальны. Иными словами, для любых i=j верно, что либо Si=Sj, либо Ti=Tj
Также гарантируется, что после каждого из событий команда состоит хотя бы из одного человека
Формат вывода
Необходимо вывести N строк - по одной после обработки каждого из событий
Каждая строка должна состоять из двух значений - имени самого опытного члена команды и разности между суммарной опытностью остальных членов команды и опытностью самого опытного члена команды
Если членов команды с максимальной опытностью несколько, нужно вывести того, чье имя лексикографически минимально
Внимание! С учетом ограничений объем выводимых данных может быть достаточно большим. Имейте это в виду и позаботьтесь об эффективности вывода
Пример
Ввод
9
Ivan 1
Anton 1
Victor 2
Anton 3
Ivan 5
Denis 10
Victor 11
Anton 11
Ivan 12
Вывод
Ivan 0
Anton 0
Anton 0
Ivan -1
Victor -3
Victor -8
Denis -1
Anton -1
Ivan 1
Примечание
Разберем пример из условия
Сначала в момент времени T=1 к команде присоединяется Ivan. Он является единственным членом команды, его опытность на данный момент равна 0. Больше в команде никого нет, так что суммарная опытность оставшейся команды также равна 0. После обработки первого события добавляем к ответу Ivan 0
Следующее событие происходит также в момент времени T=1 и к команде присоединяется Anton. Оба члена команды имеют опытность 0, но Anton лексикографически меньше Ivan, поэтому после обработки этого запроса добавляем к ответу Anton 0
В момент времени T=2 к команде присоединяется Victor. Опытность Ivan и Anton теперь равна 1, опытность Victor равна 0. Разность между суммарной опытностью оставшихся членов команды и опытностью самого опытного члена команды равна (1+0)−1=0. Добавляем к ответу Anton 0
^^^ - Как понимать это умозаключение?
"Опытность Ivan и Anton теперь равна 1" - значит, суммарная опытность оставшихся членов команды как минимум 2.
А авторы почему-то написали (1 + 0) - 1 = 0, хотя по логике вещей должны были написать (1 + 1) - 1 = 1.
Что я не догнал???
Походу, понял. Ребята из Яндекса не написали в условии задачи, как определяется самый опытный. Зато написали в формате вывода: "Если членов команды с максимальной опытностью несколько, нужно вывести того, чье имя лексикографически минимально".
За этой фразой, видимо, скрывается мысль, что этот принцип используется не только при выводе. Видимо, подразумевалось, что данный принцип надо использовать и в других местах программы.
Поэтому я, наивный, и не понял, что когда считается опытность самого опытного члена, то если получается более одного члена с одинаково высоким опытом, то надо выбрать лексикографически самого опытного, и суммарный опыт посчитать без этого человека.
В момент времени T=3 Anton уходит из команды. Теперь команда состоит из Ivan с опытностью 2 и Victor с опытностью 1. Самым опытным является Ivan, а разность между суммарной опытностью оставшихся членов команды и его опытностью равна 1−2=−1. Добавляем к ответу Ivan −1
В момент времени T=5 уходит Ivan. Теперь в команде только Victor с опытностью 3, разность равна 0−3=−3. Добавляем к ответу Victor −3
В момент времени T=10 к команде присоединяется Denis. Victor накопил опытность 8, а опытность Denis пока равна 0. Разность равна 0−8=−8. Добавляем к ответу Victor −8
В момент времени T=11 Victor уходит из команды. В команде остается только Denis с опытностью 1, разность равна 0−1=−1. Добавляем к ответу Denis−1
Также в момент времени T=11 в команду возвращается Anton. Суммарно с его предыдущим периодом работы, Anton накопил опытность 2, тогда как у Denis опытность 1. Разность равна 1−2=−1. Добавляем к ответу Anton −1
Следом в момент времени T=12 в команду возвращается Ivan. С учетом предыдущего периода работы у Ivan опытность 4, у Anton опытность 3, а у Denis опытность 2. Разность равна 5−4=1. Добавляем к ответу Ivan 1
Ограничение памяти
256.0 Мб
Ограничение времени
7 с
Ввод
Стандартный ввод или input.txt
Вывод
Стандартный вывод или output.txt
Попытка решения
Так как в примечании разобран пример, в котором есть утверждения, которые я не смог сразу понять (а спросить и уточнить было не у кого), то здесь публикуется неправильное решение. С учетом текстовой вставки выше, в резделе примечания, этот пример можно доработать.
#!/usr/bin/python3
# Структура хранения учетных данных для человека
class HumanData:
def __init__(self, name):
self.name = name # Имя для удобства, можно не хранить
self.exp = 0
self.lastIncomeTime = 0
# Перечень имен текущих человек в команде
crew=[]
# Состояния человеков
humans={}
def registration(name, time):
# Запоминаются учетные данные человека, если они еще на были созданы
if name not in humans:
humanData=HumanData(name)
humans[name]=humanData
# У людей в команде обновляется опыт
for currName in crew:
appendExp=time - humans[currName].lastIncomeTime
humans[currName].exp+=appendExp
humans[currName].lastIncomeTime=time
# Надо определить, приходит человек или уходит
if name in crew:
isIncome=False # Уходит, т. к. он уже был в команде
# Исключается из команды
crew.remove(name)
### Сколько человек пробыл в команде, теперь в начале итерации
### appendExp=time - humans[name].lastIncomeTime
### Добавляется опыт, теперь в начале итерации
### humans[name].exp+=appendExp
else:
isIncome=True # Приходит
# Запоминается время прихода
humans[name].lastIncomeTime=time
# Человек включается в команду
crew.append(name)
# Определяется самый опытный член команды,
# в которой уже исключен текущий человек
# если он уходит
# Заодно считается и лучший опыт
bestName=""
bestExp=0
collectiveExp=0
for currName in crew:
currExp=humans[currName].exp
collectiveExp+=currExp
if currExp>bestExp:
bestName=currName
bestExp=currExp
# collectiveExp=collectiveExp-bestExp
if bestExp==0:
bestName=name
# Если человек уходит, его уже нет в команде
# но его тоже надо сравнить с лучшим из оставшихся
if not isIncome:
if humans[name].exp>bestExp:
bestName=name
bestExp=humans[name].exp
result=collectiveExp-bestExp
print(f"{bestName} {result}")
def solution(fRead):
# Загрузка данных
n = int( fRead.readline().strip() )
for i in range(n):
line=fRead.readline().strip().split()
name=line[0]
time=int(line[1])
# print(f"Load {name}:{time}")
registration(name, time)
with open('input.txt', 'rt') as fRead:
solution(fRead)
