2329. Колокол

Напишите программу, которая в массиве из n целых чисел наименьший элемент поставит на первое место, наименьший из оставшихся – на последнее, следующий по величине – на второе место, следующий – на предпоследнее и так далее – до середины массива.

Вход. В первой строке записано целое число n (1 ≤ n ≤ 30000). Во второй строке записаны n элементов массива, каждый из которых по модулю не больше 32767.

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

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

РЕШЕНИЕ

сортировка

Анализ алгоритма

Отсортируем входной набор чисел. Далее установим два указателя – на начало и на конец отсортированного массива. Строим новый массив, попеременно передвигая указатели к середине массива.

Реализация алгоритма

Входной и выходной массивы будем хранить в m и res.

#define MAX 30010

int m[MAX], res[MAX];

Читаем входной массив.

scanf("%d",&n);

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

scanf("%d",&m[i]);

Сортируем набор чисел.

sort(m,m+n);

Устанавливаем указатели на начало и на конец массива.

left = 0; right = n - 1;

Строим новый массив, попеременно передвигая указатели к середине массива. Если i четно, то ставим m[i] в начало, если i нечетно – то ставим m[i] в конец.

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

if (i % 2 == 0)

res[left++] = m[i];

else

res[right--] = m[i];

Выводим полученный массив.

printf("%d",res[0]);

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

printf(" %d",res[i]);

printf("\n");

Реализация с квадратическим временем сортировки

Решение с квадратическим временем сортировки не проходит по времени

#include <stdio.h>

#define MAX 30010

int m[MAX], res[MAX];

int i, j, n, temp, left, right;

int main(void)

{

scanf("%d",&n);

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

scanf("%d",&m[i]);

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

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

if (m[i] > m[j])

{

temp = m[i];

m[i] = m[j];

m[j] = temp;

}

left = 0; right = n - 1;

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

if (i % 2 == 0)

res[left++] = m[i];

else

res[right--] = m[i];

printf("%d",res[0]);

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

printf(" %d",res[i]);

printf("\n");

return 0;

}