Сортировки

Новые методы работы со списками.

A.pop() — удалить последний элемент из списка. A.pop(i) — удалить из списка элемент с индексом i.

A.insert(i, val) — вставить в список A в позицию с индексом i элемент со значением val. Элементы, которые раньше имели индексы i и более сдвигаются вправо.

Копирование списков

Присваивание B = A не создает новый список, а всего лишь делает B ссылкой на уже существующий список. Для создания копии списка можно использовать срезы:

B = A[:]

Упражнения

E: Сортировка по невозрастанию

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

1 4 2 3 4

4 4 3 2 1

F: Сортировка по неубыванию

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

1 4 2 3 4

1 2 3 4 4

ZB: Слияние

Даны два списка целых чисел. Каждый из них упорядочен в порядке неубывания чисел.

Объедините эти два списка в один так, чтобы числа в нем шли также в порядке неубывания.

Гарантируется, что числа исходных списков по модулю не превосходят миллиона.

1 3 3 3 4 5 8 8
2 3 5 6 11

1 2 3 3 3 3 4 5 5 6 8 8 11

ZC: Сортировка слиянием

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

Решите эту задачу при помощи алгоритма сортировки слиянием.

1 4 2 3 4

1 2 3 4 4

O: Сортировка подсчетом

Дан список из N (N≤10⁵) элементов, которые принимают целые значения от 0 до 100.

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

1 3 2 3 1

1 1 2 3 3

J: Результаты олимпиады

В олимпиаде участвовало N человек. Каждый получил определенное количество баллов, при этом оказалось, что у всех участников — разное число баллов.

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

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

Выведите список участников (только фамилии) в порядке убывания набранных баллов.

3
Ivanov 15
Petrov 10
Sidorov 20

Sidorov
Ivanov
Petrov

ZA: "Сортировка времени"

Вводится сначала число N (1≤N≤100), а затем N моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 59) и секунды (от 0 до 59), каждый из них записан в отдельной строке.

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не обязательно).

4
10 
20 
30
7 
30 
00
23 
59 
59
13 
30 
30

7 30 0
10 20 30
13 30 30
23 59 59

K: Такси^*

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

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

В первой строке записаны N чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. Во второй строке записаны N чисел — тарифы за проезд одного километра в такси.

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

10 20 30
50 20 30

1700