1. C++ / Говнокод #19173

    0

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 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) при помощи двух стеков.

    Запостил: HiewMorjowie, 12 Декабря 2015

    Комментарии (10) RSS

    • ava guest 12.12.2015 21:03 # +2

      Хуй.
      Ответить

    • ava bormand 12.12.2015 21:14 # +3

      > scanf
      > printf
      c++
      Ответить

      • ava inkanus-gray 12.12.2015 21:18 # +2

        Но они же более универсальны, чем стандартный оператор вывода в поток.

        Где в C++ оператор, у которого можно задавать формат вывода?
        Ответить

        • ava bormand 12.12.2015 21:20 # +3

          В <iomanip>. Но писанины получается больше, да.
          Ответить

          • ava inkanus-gray 12.12.2015 21:22 # +3

            Ну вот, значит, кресты не нужны. Это ловушка, созданная для того, чтобы программистов занять ненужной работой. Примерно как в армии, когда ломом просят выкопать яму глубиной два метра.
            Ответить

            • ava bormand 12.12.2015 21:30 # 0

              Ну да. Эти стримы ещё и бинарник неплохо раздувают - каждая << превращается в вызов функции.
              Ответить

        • ava Soul_re@ver 13.12.2015 01:08 # +3

          В boost::format
          Ответить

      • ava Antervis 14.12.2015 06:00 # 0

        > std::vector
        наверное, это всё-таки с++
        Ответить

        • ava bormand 14.12.2015 06:23 # +1

          > A.resize(100500)
          Но с тем же успехом там мог стоять массив.
          Ответить

    Добавить комментарий