Задание 27 ЕГЭ по информатике · 3169CC
Последовательности и подпоследовательностиВысокаяКЭС 3.2КЭС 3.16
Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i<j<k.
Определите в последовательности S три таких числа Si, Sj, Sk, что Si>Sj, Sk>Sj, и значение выражения (Si−Sj)+(Sk−Sj) максимально. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Дано два входных файла — файл A и файл B. Каждый из них в первой строке содержит число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000.
Для каждого файла найдите максимальное значение выражения (Si−Sj)+(Sk−Sj). При обработке файла B нельзя использовать переборный алгоритм, вычисляющий величину для всех возможных троек, поскольку такая программа будет выполняться слишком долго.
1_3169CC.zipОпределите в последовательности S три таких числа Si, Sj, Sk, что Si>Sj, Sk>Sj, и значение выражения (Si−Sj)+(Sk−Sj) максимально. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Дано два входных файла — файл A и файл B. Каждый из них в первой строке содержит число N (5≤N≤10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000.
Для каждого файла найдите максимальное значение выражения (Si−Sj)+(Sk−Sj). При обработке файла B нельзя использовать переборный алгоритм, вычисляющий величину для всех возможных троек, поскольку такая программа будет выполняться слишком долго.
Показать ответ
957; 1292
Подсказки (3)
- Как выразить целевую функцию через значения элементов, стоящих слева и справа от Sj?
- (Si−Sj)+(Sk−Sj)=Si+Sk−2Sj. Для каждого среднего элемента нужно знать максимальный элемент слева и максимальный элемент справа.
- Последовательно поддерживайте максимум слева, а массив или суффиксные максимумы — справа. Для каждого j вычисляйте maxLeft+maxRight−2Sj и обновляйте общий максимум.
Решение
1. Преобразуем выражение:
(Si−Sj)+(Sk−Sj)=Si+Sk−2Sj
2. При фиксированном среднем индексе j выгоднее всего выбрать максимальный элемент среди элементов с индексами меньше j и максимальный элемент среди элементов с индексами больше j.
3. Для эффективной обработки можно заранее построить массив суффиксных максимумов: Rj=max(Sj+1,…,SN). Затем пройти последовательность слева направо, поддерживая максимум Lj=max(S1,…,Sj−1).
4. Для каждого допустимого j вычисляем значение Lj+Rj−2Sj и сохраняем наибольшее. Такой алгоритм работает за O(N) времени.
5. Для файла B следует использовать потоковую обработку с двумя проходами или хранить только необходимые суффиксные максимумы, а не перебирать все тройки.
(Si−Sj)+(Sk−Sj)=Si+Sk−2Sj
2. При фиксированном среднем индексе j выгоднее всего выбрать максимальный элемент среди элементов с индексами меньше j и максимальный элемент среди элементов с индексами больше j.
3. Для эффективной обработки можно заранее построить массив суффиксных максимумов: Rj=max(Sj+1,…,SN). Затем пройти последовательность слева направо, поддерживая максимум Lj=max(S1,…,Sj−1).
4. Для каждого допустимого j вычисляем значение Lj+Rj−2Sj и сохраняем наибольшее. Такой алгоритм работает за O(N) времени.
5. Для файла B следует использовать потоковую обработку с двумя проходами или хранить только необходимые суффиксные максимумы, а не перебирать все тройки.
Частые ошибки
- Перебирать все тройки индексов, получая слишком большую сложность.
- Использовать минимум вместо максимума слева или справа.
- Забыть, что для среднего элемента $S_j$ должны существовать элементы и слева, и справа.
- Вычислять $S_i+S_k-S_j$ вместо $S_i+S_k-2S_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. Обозначим Si, Sj, Sk три…Последовательности и подпоследовательности · A6A24727Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R)…Последовательности и подпоследовательности · BDD715
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.