Задание 27 ЕГЭ по информатике · A6A247
Последовательности и подпоследовательностиВысокаяКЭС 3.2КЭС 3.16
Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i<j<k. Определите в последовательности S три таких числа Si, Sj, Sk, что Si<Sj, Sk<Sj, и значение выражения (Sj−Si)+(Sj−Sk) максимально. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000). Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Используйте данные из прилагаемых файлов.
1_A6A247.zipДаны два входных файла — файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000). Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. Используйте данные из прилагаемых файлов.
Показать ответ
788; 1284
Подсказки (3)
- Для каждого среднего элемента Sj нужно независимо максимизировать левую разность Sj−Si при i<j и правую разность Sj−Sk при k>j.
- Храните минимум среди уже просмотренных элементов слева и минимум среди элементов справа. Для фиксированного Sj значение равно 2Sj−min(Si)−min(Sk).
- Сначала найдите минимум на суффиксе справа от каждой позиции, затем одним проходом слева направо вычисляйте 2Sj−минимум слева−минимум справа и запоминайте максимум.
Решение
1. Для фиксированного среднего индекса j выражение можно преобразовать:
(Sj−Si)+(Sj−Sk)=2Sj−Si−Sk
2. При фиксированном j для максимизации выражения необходимо выбрать минимальный элемент слева от позиции j и минимальный элемент справа от позиции j.
3. Построим массив суффиксных минимумов: для каждой позиции сохраним минимальное значение среди элементов правее неё.
4. При проходе слева направо поддерживаем минимум среди уже обработанных элементов. Для каждой внутренней позиции вычисляем значение 2Sj−Lj−Rj, где Lj — минимум слева, а Rj — минимум справа.
5. Максимум вычисленных значений является ответом для файла. Алгоритм работает за O(N) времени и использует O(N) памяти; суффиксные минимумы можно вычислять и хранить в одном массиве.
(Sj−Si)+(Sj−Sk)=2Sj−Si−Sk
2. При фиксированном j для максимизации выражения необходимо выбрать минимальный элемент слева от позиции j и минимальный элемент справа от позиции j.
3. Построим массив суффиксных минимумов: для каждой позиции сохраним минимальное значение среди элементов правее неё.
4. При проходе слева направо поддерживаем минимум среди уже обработанных элементов. Для каждой внутренней позиции вычисляем значение 2Sj−Lj−Rj, где Lj — минимум слева, а Rj — минимум справа.
5. Максимум вычисленных значений является ответом для файла. Алгоритм работает за O(N) времени и использует O(N) памяти; суффиксные минимумы можно вычислять и хранить в одном массиве.
Частые ошибки
- Перебирать все тройки индексов, что имеет кубическую сложность.
- Выбирать максимальные, а не минимальные элементы слева и справа.
- Нарушать порядок индексов $i<j<k$.
- Использовать первый или последний элемент как средний, хотя по обе стороны от $j$ должны существовать элементы.
Источник: Открытый банк ФИПИ
Похожие задания
27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · 38414E27Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · 519CA027Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · 952F4627Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · A47CA127Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · BDD71527Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 04D7CD
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.