- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stdio.h>
std::vector<int> A, B, C;
void build(const std::vector<int> A, int k, int razmer){
int n = razmer;
B.resize(n);
C.resize(n);
B.front() = A.front();
C.back() = A.back();
k--;
for(int i1(1), i2(n - 2); i1 < n; i1++, i2--){
B[i1] = (i1 % k) ? std::max(A[i1], B[i1 - 1]) : A[i1];
C[i2] = ((i2 + 1) % k) ? std::max(A[i2], C[i2 + 1]) : A[i2];
}
}
int main(){
int m, count;
A.resize(100001);
scanf("%d", &m);
count = 0;
while(true){
scanf("%d", &A[count]);
if(A[count] == -1) break;
count++;
}
build(A, m, count);
int l = 0;
while(count - 1 >= m){
printf("%d\n", std::max(C[l], B[l + m - 1]));
l++;
}
return 0;
}
Код, реализующий поиск максимума по подотрезках последовательности чисел. Если непонятно, то тут строится дерево отрезков, и потом с ним происходит какая-то ебола. Красивое решение получается при использовании стандартного алгоритма поиска максимума в очереди за O(1) при помощи двух стеков.