Ответы пользователя по тегу C++
  • Как решить подобную задачу? ЕГЭ 2014 информатика

    @oxygen3
    Тоже писал эту задачу. Поддерживал минимум на префиксе. Стресс-тест дома программа прошла, правда в бланке из-за того, что писал на Pascal, а не на C++ написал for i := 1 to n по привычке, а надо было условие i < n, то есть до n-1;
    Итак, если мы находимся в элементе с номером i, то minpref - минимум на отрезке от 1 до i-6, который мы поддерживаем (в каждой итерации смотрим на элемент, который был 6 итераций назад и если a[i-6] < minpref то minpref = a[i-6]), и если a[i] * minpref < minout, то minout = a[i] * minpref. Как сделать это с памятью O(n) очевидно, у меня написан костыль, который работает с константной памятью(массив a), можно было использовать стандартную очередь, но за нее бы не поставили максимум баллов по критериям.
    Время работы - O(n).
    Кусок с считыванием от 0 до 5 можно запихать и в основной цикл, если предварительно всё заполнено +inf.

    Если не понятно, то могу какие-то моменты разъяснить.

    Собственно код:
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    double a[6];
    
    int main(void){
        int i,n;
        double minpref = 1000000, minout = 1000000, xcur, a[5];
    
        cin >> n;
        for (int i = 0; i <= 5; i++)
            cin >> a[i];
    
        for (int i = 6; i < n; i++){
            cin >> xcur;
            minpref = min(minpref, a[i % 6]);
            a[i % 6] = xcur;
            minout = min(minout, xcur * minpref);
        }
        cout << minout << "\n";
        return 0;
    }
    Ответ написан