Матч 314, Стоящие в ряд (StandInLine)

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

 

В гарнизоне находятся n солдат и каждое утро они выстраиваются в линию в произвольном порядке. Все они имеют разный рост, который принимает значения от 1 до n. Утром солдат с ростом i помнит лишь количество солдат, стоявших слева на построении от него и имевших больший рост. Это количество равно left[i]. Необходимо определить расположение солдат на построении.

 

Класс: StandInLine

Метод: vector<int> reconstruct(vector<int> left)

Ограничения: left содержит от 1 до 10 элементов, 0 £ left[i] £ n – i - 1.

 

Вход. Массив left содержит информацию о солдатах, описанную выше.

 

Выход. Массив, содержащий рост солдат в шеренге слева направо на построении.

 

Пример входа

left

{2, 1, 1, 0}

{ 0, 0, 0, 0, 0 }

{ 6, 1, 1, 1, 2, 0, 0 }

 

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

{4, 2, 1, 3}

{1, 2, 3, 4, 5}

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

 

 

 

РЕШЕНИЕ

комбинаторика

 

Массив, содержащий расположение солдат на построении, представляет собой перестановку чисел от 1 до n. Массив left является таблицей инверсий этой перестановки. В задаче требуется по таблице инверсий восстановить саму перестановку.

В массив res, который будет содержать результирующую перестановку, будем последовательно заносить все числа с наибольшего (n) до наименьшего (1). При этом каждый раз число i + 1 будем вставлять после left[i] - го элемента в массив res, i = n – 1, n – 2, …, 0.

 

ПРОГРАММА

 

#include <cstdio>

#include <vector>

using namespace std;

 

class StandInLine

{

public:

  vector<int> reconstruct(vector<int> left)

  {

    vector<int> res;

    for(int i = left.size() - 1; i >= 0; i--)

       res.insert(res.begin() + left[i], i + 1);

    return res;

  }

};