Поиск лучшей пары элементов

Общая идея

Переберем один элемент пары. Смотрите задачи, чтобы понять, как быстро найти другой.

Задача 8513

Условие

По каналу связи передаётся последовательность целых неотрицательных чисел – показания прибора, полученные с интервалом в 1 мин. в течение T мин. (T – целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения. Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее K мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.

Разбор

Создадим массив mx, где mx[i] = max(a[1], a[2], .., a[i - 1], a[i]). Пусть нам нужно выбрать два элемента i, j такие что i - j >= k и a[i] + a[j] максимально, i переберем а a[j] = max(a[1], a[2], a[i - k - 1], a[i - k]) то есть mx[i - k].

Код 


        

        

            

        

    
        

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

        

    


    

        
 Задача 9755 

        

            
 Условие 

            
                По каналу связи передаётся последовательность целых чисел – показания прибора. В течение N мин. (N – натуральное число)
                прибор ежеминутно регистрирует значение силы тока (в условных единицах) в электрической сети и передаёт его на сервер.
                Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин., а сумма
                этих
                чисел была минимально возможной. Запишите в ответе найденную сумму.
            
        

        

            
 Разбор 

            
                Создадим массив pref_mn, где pref_mn[i] = min(a[1], a[2], .., a[i - 1], a[i]).
                Также создадим массив suf_mn, где suf_mn[i] = min(a[i], a[i + 1], ..., a[n - 1], a[n]).
                Будем перебирать элемент который стоит по центру.
                Cлева от i на расстоянии не менее k нужно взять минимальный элемент.
                И справа от i на расстоянии не менее k нужно взять минимальный элемент.
                В нашем решении это будут соответственно значения pref_mn[i - k - 1], suf_mn[i + k + 1].
            
        

    
        
 Код 

        

            

        

        

            

        

        
        

            
  Похожие задачи:  9757, 9078