Матч 307, Частичная сортировка (PartSorting)

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

Имеется массив различных элементов data, содержащий некоторую последовательность чисел. В последовательности можно менять местами соседние элементы. Сделав не более nSwaps таких перестановок, необходимо получить лексикографически наибольшую последовательность.

Из двух перестановок a и b одинаковой длины a считается больше b, если существует такой индекс i (0 £ i < n, n – размер массивов a и b), что a₁ = b₁, …, a_i-1 = b_i-1, a_i > b_i.

Класс: PartSorting

Метод: vector<int> process(vector<int> data, int nSwaps)

Ограничения: data содержит от 1 до 50 элементов, 1 £ data[i] £ 10⁶, 0 £ nSwaps £ 10⁶.

Вход. Массив различных чисел data и наибольшее допустимое количество обменов пар соседних элементов nSwaps.

Выход. Лексикографически наибольшая последовательность, которую можно получить из data, последовательно сделав не более nSwaps перестановок соседних элементов.

Пример входа

data	nSwaps
{10, 20, 30, 40, 50, 60, 70}	1
{3, 5, 1, 2, 4}	2
{19, 20, 17, 18, 15, 16, 13, 14, 11, 12}	5

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

{20, 10, 30, 40, 50, 60, 70}

{5, 3, 2, 1, 4}

{20, 19, 18, 17, 16, 15, 14, 13, 12, 11}

РЕШЕНИЕ

жадный алгоритм

Ищем максимальный элемент в массиве и двигаем в начало, меняя его с соседними элементами. Затем второй по величине элемент двигаем на второе место. Процесс совершаем до тех пор, пока не будет сделано nSwaps перестановок, или все элементы массива не будут находиться в невозрастающем порядке.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class PartSorting

{

public:

vector<int> process(vector<int> data, int nSwaps)

{

int i, MaxPos = 0, max, CurPos = 0;

while(nSwaps > 0)

{

if (CurPos >= data.size()) break;

for(max = 0, i = CurPos; i <= CurPos + nSwaps; i++)

{

if (i >= data.size()) break;

if (data[i] > max) max = data[i], MaxPos = i;

}

for(i = MaxPos; i > CurPos; i--) swap(data[i],data[i-1]);

nSwaps -= (MaxPos - CurPos); CurPos++;

}

return data;

}

};