Форум » Массивы, сортировка, работа с файлами » Задача 26-6794 не сходится половина ответа » Ответить
Задача 26-6794 не сходится половина ответа
gutgut: Условие задачи (№ 6794) (А. Рогов) В отделении банка используется система распознавания лиц, с помощью которой фиксируется время, когда посетитель пришел в отделение и время, когда он вышел. Для удобства время хранится как целое число, показывающее, сколько секунд прошло от начала суток до события. Посетителей банка обслуживают операторы, которые пронумерованы, начиная с 1. Посетитель обслуживается свободным оператором с минимальным номером. Оператор может принять следующего посетителя в ту же секунду, как обслуживаемый им посетитель покидает здание. На обслуживание требуется, как минимум, одна секунда. Если свободных операторов нет, посетитель становится в очередь. Посетитель может не дождаться своей очереди и уйти. Определите, сколько посетителей было обслужено операторами и номер оператора, обслужившего последнего посетителя. ... Моя программа [pre2] f=open('26-132.txt') n,k=map(int,f.readline().split()) D=[] for line in f.readlines(): t,tend = line.split() D+=[(int(t),int(tend))] f.close() oper=k*[0] # время освобождения операторов D.sort(key=lambda x : x[0]) count=0 for t, tend in D: tmin=min(oper) imin=oper.index(tmin) if tmin<tend: count+=1 oper[imin]=tend last=imin print(count,last+1) [/pre2] Результат: 2108 177. Количество обслуженных посетителей совпало с ответом, а номер оператора - нет. В авторском решении моделируется очередь, я этого не делаю, но ведь и так после сортировки по времени прихода посетители попадают к оператору в порядке очереди! Что я не учёл? Кто может подсказать? Кстати, на тестовом варианте исходных данных программа получила правильный результат.
Ответов - 3
Alex_R: Вероятно ошибка как раз в том, что нет очереди. Прилагаю свой вариант решения: [pre2]with open('Files/26-132.txt') as f: n, k = tuple(map(int, f.readline().split())) visitors = sorted([tuple(map(int, x.split())) for x in f]) operators = [-1] * k queue = [] last = 0 count = 0 events_log = [] # Заполним лог событий for i in range(len(visitors)): arrive, leave = visitors events_log.append((arrive, 1, i)) # 1 пришел events_log.append((leave, -1, i)) # -1 ушел # Сортировка лога по времени события events_log.sort() # Перебор событий for event in events_log: # Пришел посетитель if event[1] > 0: # Добавить в очередь queue.append(event) # Ушел посетитель else: try: # Освободить оператора, если посетитель был у него на приеме operators[operators.index(event[2])] = -1 except ValueError: # Если у оператора не найден, то удалить из очереди for q in queue: if q[2] == event[2]: queue.remove(q) break # Когда ушел из очереди оператор не освободился continue # Распределить посетителей из очереди по операторам for i in range(operators.count(-1)): if len(queue): count += 1 last = operators.index(-1) operators[last] = queue.pop(0)[2] # Опреатору записать номер посетителя else: break print(count, last + 1)[/pre2]
Ж: Вот еще вариант кода: [pre2] f=open('26-132.txt') [n,k]=list(map(int,f.readline().split())); print(n,k) s=[list(map(int,c.split())) for c in f.readlines()] kol=0; op=[0]*k while s: s=sorted([c for c in s if c[1]>min(op)]) # сортируем клиентов, которым есть смысл дожидаться очереди c=s[0] # время первого в очереди клиента minop=min(op) # время ближайшего освобождения оператора for i in range(len(op)): if minop > c[0]: s[0][0]=min(op) # если все заняты, то ждем первого освободившегося if op<=c[0]: op=c[1]; s.remove(c) # если кто-то свободен, то идем к нему (и исчезаем из очереди) kol+=1; print(f'обслужено клиентов:{kol}, последний обслуженный № { i+1}, {c}') break [/pre2]
gutgut: Меня всё время мучил вопрос, зачем нужна очередь, если посетители и так стоят в очереди. Наконец, я понял, в чём моя ошибка. Я назначал очередному посетителю того оператора, который освободится первым (первого по времени), но не учел, что если к моменту прихода посетителя есть несколько свободных операторов, то из них нужно выбрать первого по номеру. Привожу исправленный вариант программы, который получает нужный результат, но не использует структуру очереди. [pre2] f=open('26-132.txt') n,k=map(int,f.readline().split()) D=[] for line in f.readlines(): t,tend = line.split() D+=[(int(t),int(tend))] f.close() oper=k*[0] # время освобождения операторов D.sort() count=0 for t, tend in D: tmin=min(oper) if tmin<=t: # выбираем "минимального" из свободных операторов V=[j for j in range(k) if tmin<=oper[j]<=t] imin=min(V) count+=1 oper[imin]=tend last=imin elif tmin<tend: # выбираем того, кто первый освободится imin=oper.index(tmin) count+=1 oper[imin]=tend last=imin print(count,last+1) [/pre2]
полная версия страницы