Поиск лучшего подотрезка

Общая идея

В этих задачах обычно понятно как их решать "за квадрат". Но это долго.

Для ускорения либо используем метод двух указателей(когда для любого l верно, что если есть отрезки [l,r] и [l+1, r2], то r2>=r).

Либо насчитываем префиксные суммы, перебираем правую границу отрезка и ищем для неё подходящие левые.

Задача 9848

Условие

Геодезист измеряет высоту над уровнем моря (в миллиметрах) относительно уровня начала дороги, для каждой из N её метровых отметок. Нумерация отметок начинается с единицы. Проектировщикам необходимо выбрать участок дороги длиной не менее К метров, на котором значение суммы всех высот, выраженное в миллиметрах, максимально. Это значение называется оценкой участка дороги. Начало и конец искомого участка совпадают с метровыми отметками на дороге. Началом участка считается метровая отметка дороги с меньшим номером. Определите две метровые отметки дороги так, чтобы расстояние между ними было не менее К метров, а оценка соответствующего участка дороги — максимально возможной. Укажите в ответе найденное числовое значение максимальной оценки, выраженное в миллиметрах.

Разбор

Создадим массив pref, где pref[i] - сумма на префиксе длины i. Сумма на отрезке [l, r] теперь считается как pref[r] - pref[l - 1], поэтому если нам надо ее максимизировать то нам надо минимизировать pref[l - 1]. Поэтому также создадим второй массив mn_pref, где mn_pref[i] - минимальный pref[j] среди всех j <= i. Будем перебирать правую границу и так как длина отрезка должна быть не менее k, то возьмем mn_pref[r - k].

Код 


        

        

            

        

        
        

            
  Похожие задачи:  8570, 7046

        

    


    

        
 Задача 2109 

        

            
 Условие 

            
                Дана последовательность из N натуральных чисел. Рассматриваются последовательности подряд идущих чисел,
                которые образуют
                возрастающую арифметическую прогрессию с шагом K>=1, при этом сумма всех чисел, входящих в прогрессию
                делится на 7 (при
                этом такая прогрессия может входить в состав более длинной прогрессии).Вывести максимальную длину такую
                последовательности.
            
        

        

            
 Разбор 

            
                Будем перебирать левую границу нашего отрезка. Дальше будем перебирать первый элемент в нашей арифметической
                прогрессии.
                Зафиксируем d - шаг текущей арифметической прогрессии.
                Закинем в массив b арифметическую прогрессию которая начинается в индексе l (в массиве b индексация с 1).
                Теперь задача свелась к тому, что для массива b надо найти подотрезок максимальной суммы, такой что сумма
                кратна 7.
                Создадим массив pref, где pref[i] - сумма на префиксе длины i в массиве b.
                Сумма на отрезке [l, r] это pref[r] - pref[l - 1], и она кратна 7 когда pref[r] % 7 == pref[l - 1] % 7.
                Создадим массив mn, где mn[i] - минимальная левая граница такая что pref[l - 1] % 7 == i.
            
        

    
        
 Код 

        

            

        

        

            

        

    
        

            
  Похожие задачи:  2133 

        

    


    

        
 Задача 2581

        

            
 Условие 

            
                На вход программе подается последовательность целых чисел. Особым называется положительное четное число.
                Рассматриваются
                все непрерывные подпоследовательности исходной последовательности, содержащих ровно одно особое число.
                Программа должна
                вывести одно число – максимальную сумму такой подпоследовательности. Гарантируется, что в последовательность
                существует
                хотя бы одно особое число.
            
        

        

            
 Разбор 

            
                Будем решать задачу с помощью метода двух указаталей, i будет указывать на левую границу текущего отрезка и
                будем
                двигать j пока на отрезке [i, j] одно положительное четное число и попутно обновлять сумму.
                Когда дивагем левую границу надо вычесть из cnt 1 если a[i] - четное положительное число и также из суммы
                вычесть a[i].
            
        

    
        
 Код 

        

            

        

        

            

        

    
        

            
  Похожие задачи:  2582, 2903

        

    


    

        
 Задача 7015

        

            
 Условие 

            
                Трендовый робот «Zigzag» перемещается по плоскости. Для описания его траектории движения используется последовательность
                чисел. Считается, что робот перемещается по зигзагообразной траектории, если подпоследовательность чисел удовлетворяет
                одному из условий:
                
                
1) A1>A2<A3>…<An-1>An

                
 2) A1>A2<A3>…>An-1<An 

                
 3) A1<A2>A3<…>An-1<An 

                
 4) A1<A2>A3<…<An-1>An 

                
                Определите длину самой длинной зигзагообразной траектории.
            
        

        

            
 Разбор 

            
                Будем решать задачу для первого и второго случая.
                В первом случае: зафиксируем первый элемент и создадим два флага up, down. Вначале up = true, down = false. up будет
                говорить что a[i] > a[i - 1], down соответственно что a[i] < a[i - 1]. Исходя из этого будем двигать i вправо и менять
                    местами up, down после каждого прибавление к i одного. Во втором случае: всё то же самое что и в первом случае
                    только up, down поменять местами нужно.
            
        

    
        
 Код 

        

            

        

        

            

        

        
        

            
  Похожие задачи:  6529