Матч 187, Офисная парковка (OfficeParking)

Дивизион 2, Уровень 1

Возле офиса находятся парковочные места, расположенные в линию и пронумерованные последовательно начиная с 1. В течение дня работники приезжают и уезжают на автомобилях, паркуясь на свободных местах. Необходимо по заданному множеству событий определить наименьшее количество требуемых парковочных мест. Каждое событие задается строкой, имеющей вид: “<имя сотрудника> <arrives / departs>”.

Класс: OfficeParking

Метод: int spacesUsed(vector<string> events)

Ограничения: каждый элемент массива events содержит от 9 до 50 букв латинского алфавита.

Вход. Массив событий прибытия и отправления автомашин events.

Выход. Наименьшее требуемое количество парковочных мест на стоянке.

Пример входа

events

{“Alice arrives","bob arrives","Alice departs",

"Charles arrives","bob departs","Charles departs"}

{"AdminBrett arrives","lbackstrom arrives","AdminBrett departs",

"mike arrives", "TheFaxman arrives","AdminBrett arrives",

"lbackstrom departs","dok arrives", "AdminBrett departs",

"gt arrives","AdminBrett arrives","lbackstrom arrives",

"AdminBrett departs","jhughes arrives","jhughes departs",

"TheFaxman departs", "MaryJoe arrives","AdminBrett arrives",

"AdminBrett departs","AdminBrett arrives"}

Пример выхода

2

6

РЕШЕНИЕ

элементарные вычисления

В задаче достаточно найти момент, когда одновременно прибыло на стоянку максимальное количество автомобилей. Для этого заведем переменную c, в которой будем отслеживать число работников, прибывших в офис. С прибытием работника увеличиваем c на 1, с отъездом – уменьшаем на 1. Наибольшее значение, принимаемое переменной c, храним в max. После обработки всех событий требуемое число парковочных мест находится в переменной max.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class OfficeParking

{

public:

int spacesUsed(vector<string> events)

{

char who[50], event[10];

int max, i, c;

for(max = c = i = 0; i < events.size(); i++)

{

sscanf(events[i].c_str(),"%s %s",who,event);

if (!strcmp(event,"arrives")) c++; else c--;

if (c > max) max = c;

}

return max;

}

};