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

    • Хуй.
      Ответить
    • > scanf
      > printf
      c++
      Ответить
      • Но они же более универсальны, чем стандартный оператор вывода в поток.

        Где в C++ оператор, у которого можно задавать формат вывода?
        Ответить
        • В <iomanip>. Но писанины получается больше, да.
          Ответить
          • Ну вот, значит, кресты не нужны. Это ловушка, созданная для того, чтобы программистов занять ненужной работой. Примерно как в армии, когда ломом просят выкопать яму глубиной два метра.
            Ответить
            • Ну да. Эти стримы ещё и бинарник неплохо раздувают - каждая << превращается в вызов функции.
              Ответить
        • В boost::format
          Ответить
      • > std::vector
        наверное, это всё-таки с++
        Ответить
        • > A.resize(100500)
          Но с тем же успехом там мог стоять массив.
          Ответить

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