Матч
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;
}
};