1457. Станция
"Сортировочная"
На
железнодорожной станции Сортировочная на пути находятся n товарных вагонов, из
которых необходимо сформировать состав. Все вагоны имеют одинаковую длину,
однако в них размещены различные грузы, поэтому вагоны могут иметь разную
массу. Работники железнодорожной станции Сортировочная должны выстроить вагоны
в порядке возрастания масс тогда составу будет разрешено отправиться в путь.
Обычно для таких
целей используются так называемые маневровые тепловозы и электровозы, однако на
этой станции ведутся испытания экспериментального устройства для сортировки
вагонов. Предполагается, что оно позволит существенно сократить затраты времени
на формирование составов.
Это устройство
на воздушной подушке перемещается над вагонами, его длина немного превышает
длину двух вагонов. Оно может зависнуть над двумя соседними вагонами, поднять
их оба в воздух и поменять местами. Однако, грузоподъемность устройства
ограничена указанную операцию оно может выполнить только, если суммарная масса
двух вагонов не превышает M.
Ваша задача
состоит в том, чтобы написать программу, которая определит, можно ли с помощью
экспериментального устройства для сортировки вагонов расставить вагоны,
находящиеся на пути, в необходимом порядке.
Вход. Первая строка
содержит число вагонов n (2 ≤ n ≤ 105) и
грузоподъемность экспериментального устройства M (2 ≤ M ≤ 109).
Вторая строка содержит массы вагонов m1,
m2, ..., mn (для этих масс выполняются
неравенства 1 ≤ mi
≤ 109, кроме этого массы вагонов попарно различны). Массы вагонов
перечислены в том порядке, в котором вагоны исходно стоят на пути.
Выход. Выведите “Yes”, если с помощью
экспериментального устройства для сортировки вагонов можно расставить вагоны в
необходимом порядке, и “No” иначе.
|
Пример входа |
Пример выхода |
|
4 10 5 6 3
4 |
Yes |
РЕШЕНИЕ
сортировка
Анализ алгоритма
Для сортировки
вагонов воспользуемся обменной сортировкой. Однако в задаче требуется не
отсортировать вагоны, а определить, возможна ли она. Для этого требуется для
каждой соседней пары вагонов, для которых mi
> mi+1,
поменять местами вагоны с номерами i
и i + 1. Если существует такое i, что mi > mi+1 и mi + mi+1 > M,
то сортировку произвести нельзя.
В переменной mx вычисляем максимум чисел m1, m2, …, mi.
Если очередное значение mi+1
будет меньше mx, то вагон массой mx обязательно в процессе обменной
сортировки следует поменять местами с вагоном массы mi+1. Если для некоторого i имеет место неравенство mx + mi+1
> M и при этом mx > mi+1, то
сортировка невозможна. Иначе вагоны можно упорядочить по возрастанию их масс.
Пример
Пусть M = 10. Рассмотрим слеующий пример.
Рассмотрим пятый
элемент: m[5] = 6. Максимальный
элемент mx, стоящий до него, равен 7 (m[2] = 7). Вагон с массой 6 должен стоять перед вагоном с массой
7, следовательно эти вагоны следует поменять местами. Однако это невозможно,
так как их массы больше M: m[2] + m[5] > M
или 7 + 6 > 10.
Если например на
пятой позиции стоит вагон с массой 8, то искомая перестановка возможна, так как
вагоны с массами 7 и 8 переставлять не требуется.
Упражнение
Промоделируйте
решение для следующих примеров.
Реализация
алгоритма
Читаем входные
данные. Обрабатываем последовательно массы вагонов.
scanf("%d %d",&n,&M);
while(n--)
{
scanf("%d",&val);
Сортировка вагонов невозможна, если хотя бы один раз
выполнится оператор break. В этом случае значение n будет неотрицательным.
if ((val <
mx) && (val + mx > M)) break;
if (val >
mx) mx = val;
}
Если в цикле while обработаны все
массы вагонов, то n = -1, и
сортировка вагонов возможна. Иначе расположить вагоны требуемым образом
невозможно.
if (n >= 0) printf("No\n"); else
printf("Yes\n");
Java реализация
import java.util.*;
class Main
{
public static void
main(String[] args)
{
Scanner con = new Scanner(System.in);
int n =
con.nextInt();
int M =
con.nextInt();
int max = 0;
while(n-- > 0)
{
int val = con.nextInt();
if (val <
max && val + max > M) break;
if (val >
max) max = val;
}
if (n >= 0)
System.out.println("No\n");
else
System.out.println("Yes\n");
con.close();
}
}