Задание 27 ЕГЭ по информатике · BDD715
Последовательности и подпоследовательностиВысокаяКЭС 3.2КЭС 3.16
Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L,R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R. Требуется найти такие значения номеров элементов L, M, R, где 0<L<M<R−1, чтобы разность суммы элементов подпоследовательности S(L,M) и суммы элементов подпоследовательности S(M+1,R) была максимальна. Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число N (5≤N≤10 000 000), далее записаны N целых чисел, каждое по модулю не превышает 1000. Для файла B нельзя использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов.
1_BDD715.zipПоказать ответ
122522; 150237357
Подсказки (3)
- Выразите суммы двух частей через префиксные суммы и разделите перебор по позиции M.
- Для фиксированного M нужно максимизировать сумму S(L,M) по L<M и минимизировать сумму S(M+1,R) по R≥M+2.
- Одним проходом слева направо поддерживайте максимум суммы от допустимого начала до текущей позиции, а справа налево заранее вычислите минимальные суммы от позиции до конца. Для каждого M объедините левый максимум и правый минимум.
Решение
1. Обозначим через Pi сумму первых i элементов последовательности. Тогда сумма S(L,M) равна PM−PL−1, а сумма S(M+1,R) равна PR−PM.
D=(PM−PL−1)−(PR−PM)=2PM−PL−1−PR
2. Для каждого разделителя M требуется выбрать минимальное значение PL−1 среди индексов 0≤L−1<M и минимальное значение PR среди индексов M+2≤R≤N.
3. Минимальные значения префиксных сумм слева поддерживаются при проходе слева направо. Минимальные значения PR справа можно получить массивом суффиксных минимумов или проходом справа налево.
4. Для каждого M вычисляется кандидат 2PM−min(P0,…,PM−1)−min(PM+2,…,PN), после чего выбирается максимум. Алгоритм работает за O(N) времени и использует O(N) памяти либо O(1) дополнительной памяти при двух проходах.
D=(PM−PL−1)−(PR−PM)=2PM−PL−1−PR
2. Для каждого разделителя M требуется выбрать минимальное значение PL−1 среди индексов 0≤L−1<M и минимальное значение PR среди индексов M+2≤R≤N.
3. Минимальные значения префиксных сумм слева поддерживаются при проходе слева направо. Минимальные значения PR справа можно получить массивом суффиксных минимумов или проходом справа налево.
4. Для каждого M вычисляется кандидат 2PM−min(P0,…,PM−1)−min(PM+2,…,PN), после чего выбирается максимум. Алгоритм работает за O(N) времени и использует O(N) памяти либо O(1) дополнительной памяти при двух проходах.
Частые ошибки
- Разрешают правой части состоять из одного элемента, хотя требуется $R > M + 1$.
- Используют минимум префиксной суммы с недопустимым индексом.
- Перебирают все тройки $L$, $M$, $R$, получая слишком высокую сложность.
- Путают разность сумм с суммой модулей элементов.
Источник: Открытый банк ФИПИ
Похожие задания
27Пусть 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Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 04D7CD27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 0B12A6
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.