Разберем решение олимпиадной задачи по программированию про парикмахерскую. В статье представлен алгоритм решения в текстовом виде и исходной код программы на языке C# с комментариями.
Условие задачи
В парикмахерской работает один мастер. Он тратит на одного клиента ровно 20 минут, а затем сразу переходит к следующему, если в очереди кто-то есть, либо ожидает, когда придет следующий клиент.
Даны времена прихода клиентов в парикмахерскую (в том порядке, в котором они при-ходили).
Также у каждого клиента есть характеристика, называемая степенью нетерпения. Она показывает, сколько человек может максимально находиться в очереди перед клиентом, чтобы он дождался своей очереди и не ушел раньше. Если в момент прихода клиента в очереди находится больше людей, чем степень его нетерпения, то он решает не ждать своей очереди и уходит. Клиент, который обслуживается в данный момент, также считается находящимся в очереди.
Требуется для каждого клиента указать время его выхода из парикмахерской.
Формат входного файла
В первой строке вводится натуральное число N, не превышающее 100 — количество клиентов.
В следующих N строках вводятся времена прихода клиентов — по два числа, обозначающие часы и минуты (часы — от 0 до 23, минуты — от 0 до 59) и степень его нетерпения (неотрицательное целое число не большее 100) — максимальное количество человек, которое он готов ждать впереди себя в очереди. Времена указаны в порядке возрастания (все времена различны).
Гарантируется, что всех клиентов успеют обслужить до полуночи.
Если для каких-то клиентов время окончания обслуживания одного клиента и время прихода другого совпадают, то можно считать, что в начале заканчивается обслуживание первого клиента, а потом приходит второй клиент.
Формат выходного файла
В выходной файл выведите N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-гo клиента (часы и минуты). Если на момент прихода клиента человек в очереди больше, чем степень его нетерпения, то можно считать, что время его ухода равно времени прихода.
Примеры
Алгоритм решения
Примем, что нумерация элементов в массиве начинается с нуля.
- Прочитать из входного файла первую строку (это число N).
- Создать массив длиной N для хранения времени входа клиентов в парикмахерскую (массив элементов типа Time, DateTime или что-то в этом роде). Назовем его input.
- Создать массив целых чисел длиной N для хранения степени нетерпения каждого клиента. Назовем его impatience.
- Прочитать из входного файла N строк и заполнить прочитанными данными массивы input и impatience.
- Создать массив длиной N для хранения времени выхода клиентов из парикмахерской (массив элементов типа Time, DateTime или что-то в этом роде). Назовем его output.
- В ЦИКЛЕ for от 0 до N – 1 (по i):
1. Объявим переменную целого типа k = 0. Это количество людей в очереди перед i-м клиентом.
2. Объявим переменную целого типа kN = 0. Это расстояние в рамках массива от i-го клиента до первого в очереди перед ним.
3. Найдем эти значения путем перебора элементов массива output от i – 1 до 0 (переменная цикла j) и сравнивая значения времени с input[i]. (ЕСЛИ output[j] > input[i], ТО k = k + 1 и kN = i — j).
4. ЕСЛИ степень нетерпения i-го клиента меньше k, ТО output[i] = input[i] (значит он не будет ждать и уходит); ИНАЧЕ output[i] = input[i] + 20 минут (в начале примем, что ему возможно не нужно будет ждать очереди), далее в цикле от i – 1 до i – kN по j: ЕСЛИ output[j] > input[i] (значит i-й клиент сразу после j-го), ТО output[i] = output[j] + 20 минут и выходим из цикла по j. - Вывести значения массива output в выходной файл.
Решение задачи на языке C#
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Saloon { class Program { static void Main(string[] args) { // объект для чтения данных из файла StreamReader sr = new StreamReader("saloon.in"); // читаем N int N = Convert.ToInt32(sr.ReadLine()); // создаем массивы: для времени входа клиентов в парикмахерскую и для их степени нетерпения DateTime[] input = new DateTime[N]; int[] impatience = new int[N]; // читаем данные из файла for (int i = 0; i < N; i++) { string[] client = sr.ReadLine().Split(' '); input[i] = new DateTime(1, 1, 1, Convert.ToInt32(client[0]), Convert.ToInt32(client[1]), 0); impatience[i] = Convert.ToInt32(client[2]); } // закрываем входной поток sr.Close(); // массив структур для времени выхода клиентов из парикмахерской DateTime[] output = new DateTime[N]; for (int i = 0; i < N; i++) { int k = 0; // количество людей в очереди перед i-м клиентом int kN = 0; // расстояние в рамках массива от i-го клиента до первого в очереди перед ним // найдем эти значения for (int j = i - 1; j >= 0; j--) if (output[j] > input[i]) { k++; kN = i - j; } if (impatience[i] < k) output[i] = input[i]; else { output[i] = input[i].AddMinutes(20); for (int j = i - 1; j >= i - kN; j--) if (output[j] > input[i]) { output[i] = output[j].AddMinutes(20); break; } } } // объект для вывода данных в файл StreamWriter sw = new StreamWriter("saloon.out"); // вывод результатов в файл for (int i = 0; i < N; i++) sw.WriteLine(output[i].Hour + " " + output[i].Minute); // закрываем выходной поток sw.Close(); } } } |
Поделиться в соц. сетях: