Как решить подобную задачу? ЕГЭ 2014 информатика
Тоже писал эту задачу. Поддерживал минимум на префиксе. Стресс-тест дома программа прошла, правда в бланке из-за того, что писал на 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;
}
Циклически движетесь от первого элемента к последнему, по пути считаете произведения, и если последнее посчитанное больше меньше предыдущего минимума, обновляете мин.
Может я что не так понял, но задача детская же? неужто вы изучив все сборники не смогли её написать?