tgoop.com/csharpproglib/6398
Last Update:
В кинотеатр пришли люди, и часть мест уже занята.
Места описаны массивом из нулей и единиц:
1 — место занято
0 — место свободно
Нужно найти такое место, чтобы сидящий оказался как можно дальше от ближайшего соседа.
Разбор решения
Нужно рассмотреть три типа промежутков свободных мест:
• Начало ряда — расстояние до ближайшего соседа = количество нулей
• Конец ряда — расстояние = количество нулей
• Середина — расстояние = количество нулей / 2. Целочисленное деление.
Алгоритм
1. Проходим по массиву один раз
2. Отслеживаем индекс последнего человека, которого мы встретили
3. При встрече человека вычисляем расстояние:
• Если это первый человек → берём его индекс (левый край)
• Если не первый → вычисляем (текущий_индекс - прошлый_индекс) / 2
3. После цикла проверяем правый край: n - 1 - последний_индекс
4. Возвращаем максимум из всех расстояний.
Код:
public class Solution {
public int MaxDistToClosest(int[] seats) {
int n = seats.Length;
int maxDist = 0;
int lastPerson = -1;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) {
if (lastPerson == -1) {
// Левый край
maxDist = i;
} else {
// Середина
maxDist = Math.Max(maxDist, (i - lastPerson) / 2);
}
lastPerson = i;
}
}
// Правый край
maxDist = Math.Max(maxDist, n - 1 - lastPerson);
return maxDist;
}
}Задача решается одним проходом за линейное время. Главное — правильно обработать три случая: левый край, середину и правый край.
Чтобы щёлкать такие задачи нужно знать алгоритмы. Подтянуть такую базу поможет наш курс по алгоритмам. До конца октября скидка 40%
#dotnet_challenge