С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

Как ускорить данный алгоритм нахождения минимума на отрезке? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Считать файл формата LMS http://www.cyberforum.ru/cpp-beginners/thread1173025.html
Есть файл формата LMS, нужно взять из него определенные данные, мб кто-нибудь сталкивался с таким форматом?
C++ Добавление данных в конец файла .bmp Добрый день! хочу записывать некую информацию в конец bmp файла делаю так: uchar day = 12; uchar month = 5; ushort year = 2014; http://www.cyberforum.ru/cpp-beginners/thread1173021.html
C++ Программа работает только с одним разрешением экрана, как сделать чтобы она была универсальна
Написал простенький кликер на с++, который в игре нажимает кнопочки от 1 до 9, сделал зависимости нажатия кнопочек от того что происходит на экране, ну то есть если уровень здоровья маленький, то...
Какой фигурой обозначаются в блок схеме C++
Какой фигурой обозначаются в блок схеме запись в файл/чтение из файла? к примеру: для fout.open("input.txt");? fout <<...;?
C++ Создание класса с указателем http://www.cyberforum.ru/cpp-beginners/thread1172975.html
Всем привет :) Есть такая часть задания: Нужно создать класс АВТОМОБИЛЬ, который имеет марку (указатель на строку), цвет, объем двигателя, мощность. public class Automobile { ...
C++ Как считать символ два раза char ch = ' '; cin.get(ch); нужно первый раз считать символ функцией-членом .get() которая не пропускает разделители, для того, что бы выловить переход на новую строку функцией isspace(ch); ... подробнее

Показать сообщение отдельно
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
12.05.2014, 17:09
firefox123, Это для версии с очередью
REF: http://e-maxx.ru/algo/stacks_for_minima "Модификация очереди. Способ 1"
C++
1
2
3
4
5
6
7
8
9
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
44
45
46
#include <iostream>
#include <deque>
#include <vector>
#include <iterator>
#include <algorithm>
 
struct Min {
    std::deque<int> _d; 
    
    void push(int n) {
        while(!_d.empty() && _d.back() > n)
            _d.pop_back();
        _d.push_back(n);
    }   
 
    int min() const {
        return _d.front();
    }   
 
    void pop(int n) {
       if (!_d.empty() && _d.front() == n)
           _d.pop_front();
    }   
};
 
int main() {
    Min m;
    int n, k;
    std::cin >> n >> k;
 
    typedef std::istream_iterator<int> in; 
    std::vector<int> v(n);
    std::copy(in(std::cin), in(), v.begin());
 
    for (int i = 0; i < k; ++i)
        m.push(v[i]);
 
    std::cout << m.min() << '\n';
    for (int i = k; i < n; ++i) {
        m.push(v[i]);
        m.pop(v[i-k]);
        std::cout << m.min() << '\n';
    }   
 
    return 0;
}
Добавлено через 46 минут
firefox123, Версия с двумя стеками "Модификация очереди. Способ 2"
Компилировать с флагом -std=c++11
C++
1
2
3
4
5
6
7
8
9
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
44
45
46
47
48
49
50
51
#include <iostream>
#include <stack>
#include <utility>
 
struct Min {
    std::stack<std::pair<int,int>> _s1, _s2;
        
    void push(int n) {
        int min = _s1.empty() ? n : std::min(n, _s1.top().second);
        _s1.push({n, min});
    }   
 
    int min() const {
        if (_s1.empty() || _s2.empty())
            return _s1.empty() ? _s2.top().second : _s1.top().second;
        else return std::min(_s1.top().second, _s2.top().second);
    }   
 
    void pop() {
        if (_s2.empty()) {
            while (!_s1.empty()) {
                int n   = _s1.top().first,
                    min = _s2.empty() ? n : std::min(n, _s2.top().second);
                _s1.pop();
                _s2.push({n, min});
            } 
        }   
        _s2.pop();
    }   
};
 
int main() {
    Min m;
    int n, k;
    std::cin >> n >> k;
 
    for (int i = 0, e; i < k; ++i) {
        std::cin >> e;
        m.push(e);
    }   
 
    std::cout << m.min() << '\n';
    for (int i = k, e; i < n; ++i) {
        std::cin >> e;
        m.pop();
        m.push(e);
        std::cout << m.min() << '\n';
    }   
 
    return 0;
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.