Задача
Отсортируйте время согласно заданному критерию.
Входные данные
Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).
Выходные данные
Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно).
Тесты
|
№ |
Входные данные | Выходные данные |
|
1 |
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 |
|
2 |
5 12 40 45 23 56 12 7 45 34 8 23 34 2 56 45 |
2 56 45 7 45 34 8 23 34 12 40 45 23 56 12 |
|
3 |
3 23 56 45 21 45 54 6 45 23 |
6 45 23 21 45 54 23 56 45 |
Код 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; int a[101], b[101], c[101], d[101]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> c[i]; d[i] = a[i] * 3600 + b[i] * 60 + c[i]; } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (d[i] > d[j]) { swap(a[i], a[j]); swap(b[i], b[j]); swap(c[i], c[j]); swap(d[i], d[j]); } } } for (int i = 0; i < n; i++) { cout << a[i] << " " << b[i] << " " << c[i] << endl; } return 0; } |
Код 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> using namespace std; struct unsortedtime { int hours; int minutes; int seconds; }; bool operator > (const unsortedtime &a, const unsortedtime &b) { bool res = false; if (a.hours > b.hours) res = true; else if (a.hours == b.hours) { if (a.minutes > b.minutes) res = true; else if (a.minutes == b.minutes) { if (a.seconds > b.seconds) res = true; } } return res; }; int main() { int n; cin >> n; unsortedtime *a = new unsortedtime[n]; for (int i = 0; i < n; i++) { cin >> a[i].hours >> a[i].minutes >> a[i].seconds; } for (int k = 2; k <= n; k++) { for (int i = 0; i <= n - k; i++) { if (a[i] > a[i + 1]) { swap(a[i], a[i + 1]); } } } for (int i = 0; i < n; i++) { cout << a[i].hours << " " << a[i].minutes << " " << a[i].seconds << endl; } return 0; } |
Решение задачи (код 1)
Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().
Решение задачи (код 2)
Для решение задачи вторым способом создадим структуру unsortedtime. Каждый элемент в этой структуре будет соответствовать часу, минуте, секунде. После чего создадим оператор > , в котором будем сравнивать моменты времени. В случае необходимости будем менять их местами, используя функцию swap(). В результате выведем с помощью цикла моменты времени, упорядоченные в порядке неубывания.
Сортировка пузырьком устарела, стоит использовать одну из сортировок, работающих за $O(n \cdot log n)$. Хоть бы и встроенную в STL. Чтобы это сделать, придется создать структуру данных Время.