Закон трихотомии

Вид материала

Содержание

Подобный материал:

СОРТИРОВКА

В программировании часто возникает вопрос переразмещения элементов в порядке возрастания или убывания. Сортировка определяется как процесс разделения объектов по виду или сорту. На практике сортируемые значения редко являются изолированными данными. Они, как правило, входят в набор данных, который называется записью. Каждая запись содержит ключ, являющийся сортируемым значением, и сопутствующие данные, дополняющие ключ. Алгоритм сортировки, как правило, должен вместе с ключами переставлять и сопутствующие данные.

Введем на множестве ключей отношение порядка “<” таким образом, чтобы для любых трех значений a, b, c выполнялись условия линейного упорядочения:

1. Закон трихотомии. Справедливым является одно и только одно из соотношений:

a < b, a = b, a > b.

2. Закон транзитивности. Если a < b и b < c, то a < c.

Задача сортировки состоит в нахождении такой перестановки записей p₁, p₂, …p_n, в которой ключи

, …,

расположены в неубывающей последовательности:



 … 

СОРТИРОВКА С КВАДРАТИЧЕСКИМ ВРЕМЕНЕМ

Следующие алгоритмы являются медленными, их временная оценка составляет O(n²) в зависимости от количества сортируемых элементов n. Считаем, что изначально все числа находятся в массиве m. После выполнения кода, приведенного для каждого алгоритма, массив m становится упорядоченным по возрастанию.

Сортировка обменом. Если существуют два элемента, стоящих не в правильном порядке, то переставляем их. Процесс перестановки совершаем для всех пар (m[i], m[j]), для которых i < j и m[i] > m[j].

#include

int m[10] = {4, 6, 5, 8, 23, 4, 5, 6, 1, 2};

int i, j, temp, n = 10;

void main(void)

{

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

if (m[i] > m[j]) temp = m[i], m[i] = m[j], m[j] = temp;

for(i = 0; i < n; i++) printf("%d ",m[i]);

printf("\n");

}

Cортировка пузырьком. Является частным случаем обменной сортировки. Если существуют два последовательных элемента, стоящих не в правильном порядке, то переставляем их. Процесс перестановки продолжаем до тех пор, пока существуют два стоящих рядом элемента не в правильном порядке.

#include

int m[10] = {4, 6, 5, 8, 23, 4, 5, 6, 1, 2};

int i, temp, pos = 1, n = 10, Bound = n;

void main(void)

{

while (pos)

{

for(pos = i = 0; i < Bound - 1; i++)

if (m[i] > m[i + 1])

temp = m[i], m[i] = m[i + 1], m[i + 1] = temp, pos = i + 1;

Bound = pos;

}

for(i = 0; i < n; i++) printf("%d ",m[i]);

printf("\n");

}

По окончанию цикла for значение переменной pos равно 0, если перестановок не было (массив отсортирован). Иначе pos содержит номер позиции, начиная с которой элементы массива уже заняли свое требуемое положение. Переменная Bound содержит количество элементов, которое требуется еще отсортировать (часть массива от m[0] до m[Bound – 1] еще не отсортирована).

Сортировка вставками. Пусть массив m[0 ... i – 1] уже отсортирован. При вставке элемента m[i] ищем его место в отсортированном массиве. Для этого в цикле меняем его с соседним слева элементом до тех пор, пока он не займет свое место. Таким образом, все элементы в отсортированной части массива, большие m[i], сдвигаются на одну позицию вправо.

#include

int m[10] = {4, 6, 5, 8, 23, 4, 5, 6, 1, 2};

int i, j, temp, n = 10;

void main(void)

{

for(i = 1; i < n; i++)

{

for(j = i - 1; j >= 0; j--)

if (m[j] > m[j + 1]) temp = m[j], m[j] = m[j + 1], m[j + 1] = temp;

}

for(i = 0; i < n; i++) printf("%d ",m[i]);

printf("\n");

}

Сортировка выбором. Пусть массив m[0 ... i – 1] уже отсортирован. Среди оставшихся n – i элементов ищем наименьший и присваиваем его ячейке m[i].

#include

int m[10] = {4, 6, 5, 8, 23, 4, 5, 6, 1, 2};

int i, j, min, ptr, temp, n = 10;

void main(void)

{

for(i = 0; i < n - 1; i++)

{

min = m[i]; ptr = i;

for(j = i + 1; j < n; j++)

if (m[j] < min) min = m[j], ptr = j;

temp = m[i], m[i] = m[ptr], m[ptr] = temp;

}

for(i = 0; i < n; i++) printf("%d ",m[i]);

printf("\n");

}

БЫСТРАЯ СОРТИРОВКА

Быстрая сортировка основана на парадигме “разделяй и властвуй”:

1. Разделение. Массив m[a .. b] путем переупорядочения его элементов разбивается на две части m[a .. p – 1] и m[p + 1 .. b] так, что каждый элемент подмассива m[a .. p – 1] не превышает m[p], а каждый элемент подмассива m[p + 1 .. b] не меньше m[p]. Индекс p вычисляется в ходе процедуры разбиения. Элемент m[p] называется опорным.

2. Сортировка. Подмассивы m[a .. p – 1] и m[p + 1 .. b] сортируются путем рекурсивного вызова процедуры быстрой сортировки.

3. Комбинирование. Поскольку подмассивы m[a .. p – 1] и m[p + 1 .. b] сортируются на месте, для их объединения не требуются никакие действия: весь массив m[a .. b] оказывается отсортирован.

В наихудшем случае время работы алгоритма равно O(n²), хотя на практике в среднем время его работы составляет O(n log n).

#include

#define MAX 10

int m[] = {5,7,2,4,1,77,6,8,3,2};

void swap(int *i, int *j)

{

int temp = *i; *i = *j; *j = temp;

}

void QuickSort(int L, int R)

{

int q, x, i, j;

if (L < R)

{

x = m[R]; i = L - 1;

for(j = L; j < R; j++)

if (m[j] <= x) i++,swap(&m[i],&m[j]);

swap(&m[i+1],&m[R]);

q = i + 1;

QuickSort(L,q-1); QuickSort(q+1,R);

}

}

void main(void)

{

int i;

QuickSort(0, MAX-1);

for(i = 0; i < MAX; i++) printf("%d ",m[i]); printf("\n");

}

СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ БИБЛИОТЕКИ ШАБЛОНОВ STL

Сортировка массива. Сортировка элементов массива осуществляется функцией sort, описанной в библиотеке . По умолчанию сортировка производится в неубывающем порядке.

int m[] = {2,5,4,6,7,8,4};

sort(m,m+7);

Сортировка элементов вектора. Сортировать можно не только числа в массиве, но и любые объекты разных структур. Следующая программа заносит в структуру “вектор” убывающую последовательность 10, 9, …, 1 и сортирует ее по возрастанию.

vector m;

for(int i = 0; i < 10; i++) m.push_back(10 - i);

sort(m.begin(),m.end());

Сортировка пар. При сортировке пар целых чисел упорядочение происходит по первой компоненте пары. При равенстве первой компоненты производится сортировка по второй.

vector
ir > m;

int i;

for(i = 0; i < 10; i++)

{

m.push_back(make_pair(10-i,i*i));

m.push_back(make_pair(10-i,i*i-1));

}

sort(m.begin(),m.end());

for(i = 0; i < m.size(); i++) printf("%d %d\n",m[i].first,m[i].second);

Сортировка в убывающем порядке. Встроенные шаблоны greater и less, объявленные в библиотеке , можно передавать функции sort в третьем аргументе. Они позволяют сортировать объекты соответственно в возрастающем и убывающем порядках.

sort(m.begin(),m.end(),less());

sort(m.begin(),m.end(),greater());

Например, для сортировки пар целых чисел из предыдущего примера в убывающем порядке следует вызвать функцию

sort(m.begin(),m.end(),greater
int,int> >());

Собственная функция сортировки. Передавать в качестве третьего аргумента можно собственно написанные функции. Элементы a и b при вызове функции f(a, b) переставляются тогда и только тогда, когда функция f возвращает ложь (0). Рассмотрим пример сортировки элементов массива m по убыванию:

int m[] = {7,2,5,8,10,1,4,2,1,3};

int n = 10;

int f(int a, int b)

{

return a > b;

}

sort(m,m+n,f);

Сортировка строк. Строки можно сортировать таким же образом, как и числа. В следующем примере строки сортируются в лексикографическом порядке:

string m[] = {"this","hello","loyd","assa","finish"};

int n = 5;

sort(m,m+n);

Для сортировки строк в алфавитном порядке следует воспользоваться собственной функцией сортировки f. Если из двух сравниваемых слов одно является префиксом другого, то меньшим считается то, длина которого меньше. Это условие в функции f реализовано так: строка a меньше строки b тогда и только тогда, когда длина строки b больше длины их общей части.

string m[] = {"bcA","ABCa","Bac","ABc","ABCA","AbC","abC",

"BAc","BAC","ABC","AABC"};

int n = 11;

int min(int a, int b)

{

return (a < b) ? a : b;

}

int f(string a, string b)

{

int i,len = min(a.size(),b.size());

for(i=0;i
if (a[i] != b[i])

{

if (tolower(a[i]) == tolower(b[i])) return a[i] < b[i];

return tolower(a[i]) < tolower(b[i]);

}

return b.size() > len;

}

sort(m,m+n,f);

Результатом выполнения сортировки будет массив строк:

“AABC”,“ABC”,“ABCA”,“ABCa”,“ABc”,“AbC”,“abC”,“BAC”,“BAc”,“Bac”,“bcA”

Стабильная сортировка. Сортировка называется стабильной, если любые два равные элемента в процессе сортировки не меняют своего положения относительно друг друга. Ниже приведен пример сортировки букв с игнорированием верхнего/нижнего регистра.

int lt_nocase(char c1, char c2)

{

return tolower(c1) < tolower(c2);

}

char m[] = "fdBeACFDbEac";

const int n = sizeof(m) - 1;

stable_sort(m, m+n, lt_nocase);

Результатом сортировки будет последовательность "AaBbCcdDeEfF". Буквы расположены в возрастающем порядке. Относительный порядок одних и тех же букв сохранен. Например, буква ‘A’ стояла перед ‘a’ в начальной последовательности, такое же относительное положение сохранилось и в отсортированной последовательности. То же самое можно сказать о других буквах.

Частичная сортировка. STL позволяет частично сортировать элементы массива [first … last]. Функция partial_sort(first, sortEnd, last) сортирует элементы массива от first до sortEnd с временной сложностью O((last – first) log₂ (sortEnd – first)). Отсортируем первые 6 элементов массива x.

int x[10] = {3, 1, 4, 8, 5, 3, 7, 6, 3, 4};

partial_sort(x,x+6,x+10);

Сортировка слиянием (Фон-Неймана). Идея сортировки состоит в разбиении массива пополам, отдельной сортировки левой и правой части и слиянии двух отсортированных массивов в один. Временная сложность сортировки O(n log₂ n), где n – длина входного массива.

void merge(vector& a, vector& b, vector& c)

{

unsigned ai = 0, bi = 0, ci = 0;

while (bi != b.size() && ci != c.size())

if (b[bi] == c[ci])

{

a[ai++] = b[bi++];

a[ai++] = c[ci++];

}

else

if (b[bi] < c[ci]) a[ai++] = b[bi++];

else a[ai++] = c[ci++];

while (bi != b.size()) a[ai++] = b[bi++];

while (ci != c.size()) a[ai++] = c[ci++];

}

void mergeSort(vector& a)

{

if (a.size() <= 1) return;

int k = a.size() / 2;

vector b = vector(a.begin(), a.begin()+k);

vector c = vector(a.begin()+k, a.end());

mergeSort(b); mergeSort(c);

merge(a, b, c);

}

int aa[] = {2,7,5,8,10,1,4,2,1,3};

vector a(aa,aa+10);

mergeSort(a);

Функция mergeSort сортирует входной мссив a. Функция merge сливает массивы b и c в массив a.

Пример 1. Массив m содержит n целых чисел. Следует расположить сначала отрицательные, потом нулевые, а затем положительные числа. Числа одного знака должны сохранять относительное положение.

Пример входа	Пример выхода
{2,-3,0,-6,7,1,0,-2}	{-3,-6,-2,0,0,2,7,1}
{-3,7,0,-2,1,10,0}	{-3,-2,0,0,7,1,10}

int f(int i, int j)

{

return ((i <= 0) && (j >= 0));

}

stable_sort(m,m+n,f);

Пример 2. Массив m содержит n целых чисел. Следует расположить сначала отрицательные, потом неотрицательные числа. Числа одного знака должны сохранять относительное положение. Нулевые и положительные числа также должны сохранять относительное положение.

Пример входа	Пример выхода
{2,-3,0,-6,7,1,0,-2}	{-3,-6,-2,2,0,7,1,0}
{-3,7,0,-2,1,10,0}	{-3,-2,7,0,1,10,1}

int f(int i, int j)

{

return ((i < 0) && (j >= 0));

}

stable_sort(m,m+n,f);

ЗАДАЧИ

1. Сортировка поезда [Вальядолид, 299]. На железнодорожной станции находится поезд, который состоит из n вагонов, пронумерованных от 1 до n. Разрешается менять местами только соседние вагоны. Необходимо найти наименьшее количество таких операций, за которое можно отсортировать все вагоны поезда.

Вход. Первая строка содержит количество тестов. Каждый тест состоит из двух строк: первая содержит количество вагонов в поезде L (0  L  50), а вторая – перестановку чисел от 1 до L, указывая текущий порядок вагонов.

Выход. Для каждого теста вывести минимальное количество перестановок соседних вагонов, которыми можно отсортировать вагоны поезда по возрастанию (первым идет вагон с номером 1, последним – вагон с номером L).

Пример входа	Пример выхода
3	Optimal train swapping takes 1 swaps.
3	Optimal train swapping takes 6 swaps.
1 3 2	Optimal train swapping takes 1 swaps.
4
4 3 2 1
2
2 1

2. Семья Вито [Вальядолид, 10041]. У Вито большая семья в Нью-Йорке. Он хочет поселиться на улице, суммарное расстояние от которой до улиц проживания его родственников минимальна.

Вход. Первая строка содержит количество тестов. Каждый тест задается одной строкой. Первое число в строке содержит число родственников n (0 < n < 500), за которым идут номера их улиц s₁, s₂, …, s_n (0 < s_i < 30000). Расстояние между улицами с номерами s_i и s_j равно d_ij = |s_i – s_j|. На одной улице могут проживать несколько родственников.

Выход. Для каждого теста вывести минимальное суммарное расстояние от улицы Вито до улиц его родственников.

Пример входа	Пример выхода
3	2
2 2 4	4
3 2 4 6	6
3 3 1 7

3. Сортировка перестановками [Вальядолид, 10327]. В задаче требуется отсортировать массив чисел. При этом разрешается совершать лишь одну операцию: менять местами два соседних числа. Необходимо найти минимальное число таких перестановок, в результате которых массив чисел будет отсортирован по возрастанию.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество целых чисел n (n  1000), подлежащих сортировке. В следующей строке находятся сами n чисел.

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

Пример входа	Пример выхода
3	Minimum exchange operations : 0
1 2 3	Minimum exchange operations : 2
3
2 3 1

4. Ультра быстрая сортировка [Вальядолид, 10810]. Рассмотрим алгоритм сортировки, в котором разрешена лишь одна операция: перестановка двух соседних элементов. Эта операция производится до тех пор, пока все элементы не будут расположены в возрастающем порядке. Для заданной входной последовательности следует найти минимальное количество перестановок соседних элементов, необходимых для ее сортировки.

Вход. Состоит из нескольких тестов. Каждый тест начинается с числа n (n < 500000) – длины входной последовательности. Далее следуют n чисел, образующих входную последовательность: a₁, a₂, …, a_n (0  a_i  999999999). Последний тест содержит n = 0 и не обрабатывается.

Выход. Для каждой входной последовательности вывести минимальное количество перестановок соседних элементов, которое следует произвести для ее сортировки в возрастающем порядке.

Пример входа	Пример выхода
5	6
9	0
1
0
5
4
3
1
2
3
0

5. Детская игра [Вальядолид, 10905]. Игрок имеет n положительных чисел. Склеивая их друг с другом, можно получить разные длинные числа. Например, из чисел 123, 124, 56, 90 можно получить 24 разных числа: 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 и так далее. Число 9056124123 является наибольшим среди них.

Для заданного набора чисел следует найти максимальное число, которое можно получить в результате склейки.

Вход. Первая строка каждого теста содержит количество положительных чисел n (n  50). Во второй строке следуют сами n чисел. Последний тест содержит n = 0 и не обрабатывается.

Выход. Для каждого теста вывести наибольшее положительное число, которое можно получить в результате склейки чисел.

Пример входа	Пример выхода
3	9056124123
123 127 1239	99056124123
4	99999
123 124 56 90
5
123 124 56 90 9
5
9 9 9 9 9
0

6. Разбиение команды [Топкодер, раунд 242, дивизион 2, уровень 1]. Имеется несколько людей, которых необходимо разбить на две команды. Каждый человек обладает силой, которая хранится в массиве strengths. Выбираются два капитана, которые начинают набирать людей себе в команду. Капитаны делают свой выбор по очереди, при этом естественно выбирая себе игрока с наибольшей силой. Когда все игроки будут разбиты по командам, процесс деления игроков заканчивается. Сила команды равна суммарной силе всех ее игроков. Необходимо вычислить абсолютное значение разности сил полученных двух команд.

Класс: TeamSplit

Метод: int difference(vector strengths)

Ограничения: массив strengths содержит от 1 до 50 чисел, 1  strengths[i]  1000.

Вход. Массив strengths, содержащий силы игроков.

Выход. Абсолютное значение разности сил полученных двух команд.

Пример входа

strengths

{5,7,8,4,2}

{100}

{9,8,7,6}

{1,5,10,1,5,10}

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

4

100

2

0

7. Сортировка вставками [Топкодер, раунд 301, дивизион 2, уровень 1]. Рассмотрим алгоритм сортировки вставками. При вставке очередного элемента в упорядоченную последовательность часть элементов должна сдвигаться вправо. Например, рассмотрим сортировку массива {20,40,30,10}:

1. {20}. Число 20 ставится в ячейку с индексом 1. Сдвигов нет.

2. {20, 40}. Число 40 ставится в ячейку с индексом 1. Сдвигов нет.

3. {20, 30, 40}. Число 30 ставится в ячейку с индексом 1. Число 40 сдвигается на одну ячейку вправо.

4. {10, 20, 30, 40}. Число 10 ставится в ячейку с индексом 0. Числа 20, 30 и 40 сдвигаются вправо (три сдвига).

Таким образом, для сортировки вставками массива {20,40,30,10} следует совершить 4 сдвига. В задаче необходимо подсчитать общее количество сдвигов при сортировке вставками чисел заданного массива.

Класс: InsertionSortCount

Метод: int countMoves(vector a)

Ограничения: массив a содержит от 1 до 50 элементов, -1000  a[i]  1000, все элементы массива a разные.

Вход. Массив чисел a. Все числа в массиве разные.

Выход. Количество сдвигов элементов при сортировке вставками.

Пример входа

{20,40,30,10}

{-1,1,0}

{-1000,0,1000}

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

4

1

0

8. Сортирующая машина [Топкодер, раунд 306, дивизион 2, уровень 1]. Имеется машина для сортировки набора различных чисел. Она имеет только одну команду MOVE с одним аргументом. Эта команда переносит число, заданное в аргументе, в конец последовательности чисел.

Например, для сортировки массива чисел {19, 7, 8, 25} в возрастающем порядке следует совершить две команды:

1. MOVE 19, получим {7, 8, 25, 19}.

2. MOVE 25, получим {7, 8, 19, 25}.

Для заданного массива чисел необходимо найти наименьшее количество команд MOVE, в результате выполнения которых его элементы будут упорядочены по возрастанию.

Класс: SortMachine

Метод: int countMoves(vector a)

Ограничения: a содержит от 1 до 50 различных чисел, -1000  a[i]  1000.

Вход. Массив чисел a.

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

Пример входа

{19,7,8,25}

{1,2,3,4,5}

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

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

2

0

7

9. Частичная сортировка [Топкодер, раунд 307, дивизион 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 process(vector 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}

10. Медиана чисел [Топкодер, раунд 308, дивизион 2, уровень 1]. Медианой набора различных чисел называется такое число m, что количество чисел, больших m, равно количеству чисел, меньших m. Например, медианой множества {1, 4, 2, 5, 7} будет 4, так как существует два числа, больших 4 (числа 5 и 7), и два числа, меньших 4 (1 и 2).

Класс: MedianOfNumbers

Метод: int findMedian(vector numbers)

Ограничения: numbers содержит от 1 до 50 элементов, 1  numbers[i]  100.

Вход. Массив различных чисел numbers.

Выход. Минимальное количество операций разбиения и объединения кучек, при помощи которых можно получить из состояния startState состояние finishState. Если требуемой последовательности преобразований не существует, вывести -1.

Пример входа

numbers

{1, 4, 2, 5, 7}

{1, 5, 8, 3}

{7}

{32, 54, 27, 4, 69, 96, 73, 1, 100, 15, 21}

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

4

-1

7

32

11. Сортируемость [Топкодер, раунд 330, дивизион 2, уровень 1]. Сортируемостью массива называется среднее арифметическое сортируемости каждого его элемента. Сортируемостью элемента называется количество чисел, больших его и стоящих слева, плюс количество чисел, меньших его и стоящих справа. По заданному массиву натуральных чисел найти его сортируемость.

Класс: Sortness

Метод: double getSortness(vector a)

Ограничения: a содержит от 1 до 50 элементов, массив a содержит все числа от 1 до n (n – количество элементов в массиве a) по одному разу.

Вход. Массив чисел a.

Выход. Сортируемость входного массива.

Пример входа

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

{1,2,3}

{1,5,8,7,9,6,10,12,11,3,4,2}

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

1.25

0.0

5.166666666666667

12. Наилучшее имя [Топкодер, раунд 381, дивизион 2, уровень 1]. Определим функцию сравнения имен. Припишем вес каждой букве: ‘A’ – 1, ‘B’ – 2, …, ‘Z’ – 26. Вес имени равен сумме весов букв, входящих в него. Имя с большим весом более значимо чем имя с меньшим весом. Среди имен с одинаковым весом более значимым является то, которое идет лексикографически раньше. При этом нет лучшего имени чем JOHN, имя JOHN всегда является наиболее значимым.

Отсортировать входной массив имен в порядке убывания их значимости.

Класс: TheBestName

Метод: vector sort(vector names)

Ограничения: names содержит от 1 до 50 строк, names[i] содержит от 1 до 50 заглавных букв латинского алфавита ‘A’ – ‘Z’.

Вход. Массив имен names.

Выход. Массив имен в порядке убывания их значимости.

Пример входа

names

{"JOHN", "PETR", "ACRUSH"}

{"JOHN", "A", "AA", "AAA", "JOHN", "B", "BB", "BBB", "JOHN", "C", "CC", "CCC", "JOHN"}

{"BATMAN", "SUPERMAN", "SPIDERMAN", "TERMINATOR"}

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

{"JOHN", "ACRUSH", "PETR"}

{"JOHN","JOHN","JOHN","JOHN","CCC","BBB","CC","BB","AAA","C","AA","B","A"}

{"TERMINATOR", "SUPERMAN", "SPIDERMAN", "BATMAN"}

13. Секретарь [Топкодер, TCHS 40, уровень 1]. Имеется массив строк files, содержащий имена людей. Имена были выведены принтером в обратном порядке (вместо слова “EDWARD” печаталось “DRAWDE”). Отпечатанные слова секретарша отсортировала в лексикографическом порядке. Вернуть имя из массива files, которое будет стоять первым в отсортированном списке секретарши.

Класс: Secretary

Метод: string wrongOrdering(vector files)

Ограничения: files содержит от 1 до 50 строк, каждая из которых содержит от 1 до 50 символов ‘A’ – ‘Z’.

Вход. Массив строк files, содержащий имена людей.

Выход. Имя из массива files, которое будет стоять первым в отсортированном списке секретарши.

Пример входа

files

{"JAMES","PETER","ADAM","JOHN","DAVE","EDWARD"}

{"ALGORITHM","DESIGN","DEVELOPMENT","TCHS","STUDIO","MARATHON"}

{"AAAAA","AA","AAA"}

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

"EDWARD"

"ALGORITHM"

"AA"

УКАЗАНИЯ И РЕШЕНИЯ

1. Сортировка поезда [Вальядолид, 299]. Пусть a₁, a₂, …, a_n – перестановка множества {1, 2, …, n}. Если i < j и a_i > a_j, то пара (a_i, a_j) образует инверсию. Минимальное количество перестановок соседних вагонов, необходимое для их сортировки, равно числу инверсий во входной перестановке.

Пример. Рассмотрим второй тест. Четверка образует три инверсии, тройка – две, двойка – одну. Итого 6 инверсий. Минимальное количество перестановок, за которое можно упорядочить числа по возрастанию, равно 6:

4 3 2 1  3 4 2 1  3 2 4 1  3 2 1 4  2 3 1 4  2 1 3 4  1 2 3 4

Реализация. В переменной res подсчитываем количество инверсий в исходной перестановке и выводим результат согласно требуемому формату.

#include

void main(void)

{

int tests,i,j,n,res;

int m[50];

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

for(i=0;i
res = 0;

for(i=0;i
for(j=i+1;j
if (m[i] > m[j]) res++;

printf("Optimal train swapping takes %d swaps.\n",res);

}

}

2. Семья Вито [Вальядолид, 10041]. Отсортируем номера их улиц n родственников. Нумерацию индексов улиц родственников будем вести с нуля: считаем, что входными номерами улиц являются s₀, s₁, …, s_n_-1. Если Вито поселится на улице x, то суммарное расстояние от нее до родственников равно

f(x) = |x – s₀| + |x – s₁| + … + |x – s_n_-1|

Минимум функции f(x) достигается при x = s_[_n_/2]. Таким образом, Вито должен поселиться на улице с номером s_[_n_/2]. Вычислим суммарное расстояние от улицы s_[_n_/2] до улиц s_i (1  i  n) и выведем его.

Пример. Рассмотрим третий тест. Сортируем номера улиц: 1, 3, 7. Число улиц n равно 3. Считаем, что s₀ = 1, s₁ = 3, s₂ = 7. Номер улицы Вито равен s_[_n_/2] = s₁ = 3. Суммарное расстояние до родственников равно f(3) = |1 – 3| + |3 – 3| + |7 – 3| = 2 + 0 + 4 = 6.

Реализация. В массиве m храним номера улиц родственников s_i. При этом m[i] = s_i_+1,0  i  n – 1_. Для каждого теста вводим значения входных данных, сортируем номера улиц родственников (массив m). Вычислим сумму расстояний от оптимального номера улицы Вито с номером s_[_n_/2] до всех остальных улиц и выведем ее.

#include

#include

using namespace std;

int m[500];

int tests, i, n, s;

void main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&m[i]);

sort(m, m + n);

for(s = i = 0; i < n; i++)

s += abs(m[n/2] - m[i]);

printf("%d\n",s);

}

}

3. Сортировка перестановками [Вальядолид, 10327]. Пусть a₁, a₂, …, a_n – некоторая последовательность чисел. Если i < j и a_i > a_j, то пара (a_i, a_j) называется инверсией. Минимальное количество перестановок соседних элементов, которое следует совершить для сортировки последовательности, равно числу инверсий в ней.

Пример. Для сортировки чисел со второго теста следует совершить две перестановки соседних элементов:

2 3 1  2 1 3  1 2 3

Реализация. Читаем входную последовательность из n чисел в массив m. В переменную res заносим количество инверсий во входной последовательности и выводим результат.

#include

int n, i, j, res;

int m[1000];

void main(void)

{

while(scanf("%d",&n) == 1)

{

for(i = 0; i < n; i++) scanf("%d",&m[i]);

res = 0;

for(i = 0; i < n-1; i++)

for(j = i + 1; j < n; j++)

if (m[i] > m[j]) res++;

printf("Minimum exchange operations : %d\n",res);

}

}

5. Детская игра [Вальядолид, 10905]. Занесем входные числа в массив строк. Отсортируем строки согласно правилу: строка a меньше строки b тогда и только тогда, когда строка a + b меньше строки b + a (‘+’ – операция конкатенации строк). Строки сортируются по убыванию.

Пример. Рассмотрим первый тест. Последовательность обменов чисел при сортировке имеет вид:

123	127	1239	123127 < 127123
127	123	1239	1231239 < 1239123
127	1239	123	конец

Реализация. В символьный массив m будем считывать очередное входное число. Все входные числа храним в массиве строк s.

#include

#include

#include

using namespace std;

char m[100];

string s[100];

int i, n;

Функция f содержит функцию сортировки строк.

int f(string a, string b)

{

if (a + b > b + a) return 1;

return 0;

}

void main(void)

{

while(scanf("%d",&n),n)

{

for(i = 0; i < n; i++)

{

scanf("%s",m);

s[i] = string(m);

}

sort(s,s + n,f);

Последовательно выводим отсортированные строки. Получим наибольшее число, которое можно получить из исходных в результате склейки.

for(i = 0; i < n; i++) printf("%s",s[i].c_str());

printf("\n");

}

}

6. Разбиение команды [Топкодер, раунд 242, дивизион 2, уровень 1]. Отсортируем участников игры по возрастанию их силы. Первый капитан берет самого сильного игрока, второй – самого сильного из оставшихся. И так далее по очереди. Для нахождения разности сил команд достаточно найти разницу суммы сил игроков, стоящих на нечетных позициях (в отсортированном массиве) и сил игроков на четных позициях. Результатом будет модуль вычисленной разности.

#include

#include

#include

#include

using namespace std;

class TeamSplit

{

public:

int difference(vector strengths)

{

int i, res = 0;

sort(strengths.begin(),strengths.end());

for(i = 0; i < strengths.size(); i++)

if (i%2) res += strengths[i]; else res -= strengths[i];

return abs(res);

}

};

7. Сортировка вставками [Топкодер, раунд 301, дивизион 2, уровень 1]. Пусть уже имеется отсортированная подпоследовательность {b₁, b₂, …, b_k}. При вставке очередного, a_k₊₁ - го числа, сдвигаются те и только те элементы b_i (1  i  k), для которых a_k₊₁ < b_i. С другой стороны, элемент b_i (1  i  k) будет сдвигаться тогда и только тогда, когда будет вставляться элемент a_k₊₁, для которого a_k₊₁ < b_i. В обоих случаях сдвигу подлежит такое количество элементов исходного массива, сколько существует пар (i, j), для которых i < j и a[i] > a[j]. То есть число сдвигов равно количеству инверсий в исходной последовательности.

#include

#include

#include

using namespace std;

class InsertionSortCount

{

public:

int countMoves(vector a)

{

int i, j, res = 0;

for(i = 0; i < a.size() - 1; i++)

for(j = i + 1; j < a.size(); j++)

if (a[i] > a[j]) res++;

return res;

}

};

8. Сортирующая машина [Топкодер, раунд 306, дивизион 2, уровень 1]. Элементы отсортированного массива можно разбить на две группы. В первую группу отнесем те числа, которые не передвигались (они стоят в массиве слева), а во вторую – которые передвигались командой MOVE. Очевидно, что дважды выполнять команду MOVE с одним и тем же числом нет смысла.

Отсортируем набор входных чисел. Двигаемся слева направо по входному и отсортированному массиву при помощи указателей i и j. Если текущие элементы массивов равны (a[i] = b[j]), то этот элемент не должен передвигаться. Иначе элемент неотсортированного массива a[i] должен переноситься в конец командой MOVE.

#include

#include

#include

using namespace std;

class SortMachine

{

public:

int countMoves(vector a)

{

int i, j, res = 0;

vector b = a;

sort(b.begin(),b.end());

for(i = j = 0; i < a.size(); i++)

if (a[i] == b[j]) j++; else res++;

return res;

}

};

9. Частичная сортировка [Топкодер, раунд 307, дивизион 2, уровень 2; дивизион 1, уровень 1]. Ищем максимальный элемент в массиве и двигаем в начало, меняя его с соседними элементами. Затем второй по величине элемент двигаем на второе место. Процесс совершаем до тех пор, пока не будет сделано nSwaps перестановок, или все элементы массива не будут находиться в невозрастающем порядке.

#include

#include

#include

using namespace std;

int min(int i, int j)

{

return (i < j) ? i : j;

}

class PartSorting

{

public:

vector process(vector 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;

}

};

10. Медиана чисел [Топкодер, раунд 308, дивизион 2, уровень 1]. Отсортируем числа в массиве. Если массив содержит четное количество чисел, то медианы не существует. Иначе медианой будет средний элемент отсортированного массива.

#include

#include

#include

using namespace std;

class MedianOfNumbers{

public:

int findMedian(vector numbers)

{

int size = numbers.size();

sort(numbers.begin(),numbers.end());

return size % 2 ? numbers[size/2] : -1;

}

};

11. Сортируемость [Топкодер, раунд 330, дивизион 2, уровень 1]. Сортируемость отсортированного по возрастанию массива чисел равна нулю. Если два числа i и j в массиве стоят неправильно (образуют инверсию), то при подсчете сортируемости каждого из этих элементов следует прибавить по единице. Таким образом для решения задачи достаточно подсчитать количество инверсий в массиве, умножить полученно число на 2 и разделить на количество элементов.

#include

#include

using namespace std;

class Sortness

{

public:

double getSortness(vector a)

{

int i, j, len = a.size(), res = 0;

for(i = 0; i < len - 1; i++)

for(j = i + 1; j < len; j++)

if (a[i] > a[j]) res += 2;

return (double)res / len;

}

};

12. Наилучшее имя [Топкодер, раунд 381, дивизион 2, уровень 1]. Задача сводится к написанию функции сортировки строк f согласно заданным условиям. Строки a и b меняются местами при вызове f(a, b), если функция f возвращает ложь. Значимость имени JOHN отобразим следующим фактом: если a = JOHN, то вернем 1 (переставлять a и b не надо), если b = JOHN, то вернем 0 (a и b следует переставить).

Функция sum вычисляет вес имени. Если имя a имеет больший вес, чем b, то возвращаем 1 (a и b не переставляем). В случае равенства весов лексикографически сравниваем строки, возвращая значение a < b. В остальных случаях функция f возвращает 0.

#include

#include

#include

#include

using namespace std;

int sum(string s)

{

int i, res;

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

res += (s[i] - 'A' + 1);

return res;

}

int f(string a, string b) // true, not to swap

{

if (a == "JOHN") return 1;

if (b == "JOHN") return 0;

if (sum(a) > sum(b)) return 1;

if (sum(a) == sum(b)) return a < b;

return 0;

}

class TheBestName

{

public:

vector sort(vector names)

{

std::sort(names.begin(),names.end(),f);

return names;

}

};

13. Секретарь [Топкодер, TCHS 40, уровень 1]. Сортируем массив строк files, используя функцию сортировки f: обращаем сравниваемые строки и сравниваем их лексикографически. После чего возвращаем первое слово.

#include

#include

#include

#include

using namespace std;

int f(string a, string b)

{

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

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

return a < b;

}

class Secretary

{

public:

string wrongOrdering(vector files)

{

sort(files.begin(),files.end(),f);

return files[0];

}

};

СПИСОК ИСПОЛЬЗОВАННЫХ ЗАДАЧ

[Вальядолид] acm.uva.es/problemset:

299 (Сортировка поезда), 10041 (Семья Вито), 10327 (Сортировка перестановками), 10810 (Ультра быстрая сортировка), 10905 (Детская игра).

[Топкодер] www.topcoder.com:

SRM 242 (Разбиение команды), SRM 301 (Сортировка вставками), SRM 306 (Сортирующая машина), SRM 307 (Частичная сортировка), SRM 308 (Медиана чисел), SRM 330 (Сортируемость), SRM 381 (Наилучшее имя), TCHS 40 (Секретарь).

Blog

Закон трихотомии

Содержание

Реализация. Читаем входную последовательность из n чисел в массив m. В переменную res заносим количество инверсий во входной последовательности и выводим результат.

Пример. Рассмотрим первый тест. Последовательность обменов чисел при сортировке имеет вид:

Реализация. В символьный массив m будем считывать очередное входное число. Все входные числа храним в массиве строк s.