Матч 386, Трофейная полка (TrophyShelf)

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

На полке в ряд расположено несколько трофейных вещей. Их высоты заданы в массиве trophies. Вы смотрите на полку строго с левой стороны. Левую вещь, высота которой содержится в trophies[0], видна полностью. Каждая следующая вещь видна, если ее полностью не закрывает ни одна вещь, стоящая спереди.

Вам следует выяснить, не увеличится ли число видимых трофеев при развороте доски на 180 градусов. Вернуть вектор, первый элемент которого равен числу видимых трофеев слева, а второй – числу видимых трофеев справа.

Класс: TrophyShelf

Метод: vector<int> countVisible(vector<int> trophies)

Ограничения: trophies содержит от 1 до 50 целых чисел, 1 £ trophies[i] £ 100.

Вход. Массив trophies содержит высоты трофеев, перечисленных слева направо.

Выход. Вектор из двух элементов. Первый элемент вектора равен количеству видимых трофеев слева, а второй – количеству видимых трофеев справа.

Пример входа

trophies

{1,2,3,4,5}

{5,5,5,5}

{1,4,2,5,3,7,1}

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

{5, 1}

{1, 1}

{4, 2}

РЕШЕНИЕ

обработка массива

Функция vis(shelf) возвращает количество видимых трофеев слева на полке. Для вычисления количества видимых трофеев справа следует обернуть массив trophies при помощи функции reverse и вызвать на нем функцию vis.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int vis(vector<int> shelf)

{

int max, i, res;

for(max = i = res = 0; i < shelf.size(); i++)

if (shelf[i] > max) res++, max = shelf[i];

return res;

}

class TrophyShelf

{

public:

vector<int> countVisible(vector<int> trophies)

{

vector<int> res(2);

res[0] = vis(trophies);

reverse(trophies.begin(),trophies.end());

res[1] = vis(trophies);

return res;

}

};