Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
12.05.2014, 11:18     Как ускорить данный алгоритм нахождения минимума на отрезке? #1
Здравствуйте, подскажите, пожалуйста, почему решение не проходит по времени на нескольких тестах? Как исправить это?

Сама задача (открыть)

Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.

Формат входных данных

В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Формат выходных данных

Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.

Пример

Входные данные
7 3
1 3 2 4 5 3 1

Выходные данные
1
2
2
3
1


Мое решение (открыть)

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <set>
using namespace std;
int main() {
    int n, k, c;
    cin >> n >> k;    
    int a[n];
    multiset<int> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < k; i++) {
        m.insert(a[i]); // добавляем первые k элементов в множество
    }
    for (int i = k; i <= n; i++) {
        cout << *m.begin() << endl;  // выводим минимальный элемент
        if (i == n) break;       // выходим из цикла, когда доходим до конца массива 
        m.erase(m.lower_bound(a[i - k])); // удаляем из множества элемент, который вышел из рассматриваемого отрезка
        m.insert(a[i]);   // вставляем следующий элемент в множество     
    }
      
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2014, 11:18     Как ускорить данный алгоритм нахождения минимума на отрезке?
Посмотрите здесь:

C++ Как отправлять данный файл на данный адрес электронной почты?
C++ Непрерывные функции и нахождение минимума на отрезке
C++ Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами
Написать программу для нахождения минимума C++
Найти на отрезке [-10;10] абсциссу точки минимума функции. Исправить ошибки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
12.05.2014, 12:42     Как ускорить данный алгоритм нахождения минимума на отрезке? #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
 
int main(void)
{
    int n, k, c;
    std::cin >> n >> k;    
    int * a = new int[n];
 
    for (int i = 0; i < n; i++)
        std::cin >> a[i];
 
    int i = 0;
    while (i + k <= n)
    {
        std::cout << *std::min_element(a + i, a + k + i) << '\n';
        ++i;
    }
 
    system("pause");
    delete [] a;
    return 0;
}
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
12.05.2014, 12:49  [ТС]     Как ускорить данный алгоритм нахождения минимума на отрезке? #3
John Prick, спасибо, но все-равно не проходит тесты. В задании говорилось, что нужно использовать ассоциативный контейнер.
Миниатюры
Как ускорить данный алгоритм нахождения минимума на отрезке?  
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
12.05.2014, 13:03     Как ускорить данный алгоритм нахождения минимума на отрезке? #4
В вашем задании ничего про ассоциативный контейнер нет.
Попробуйте убрать вывод в консоль и выводите результаты в файл.
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
12.05.2014, 13:35  [ТС]     Как ускорить данный алгоритм нахождения минимума на отрезке? #5
John Prick,
Цитата Сообщение от John Prick Посмотреть сообщение
Попробуйте убрать вывод в консоль и выводите результаты в файл.
К сожалению, я не знаю, как это сделать
Цитата Сообщение от John Prick Посмотреть сообщение
В вашем задании ничего про ассоциативный контейнер нет.
Просто отдельно записана подсказка.
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
12.05.2014, 13:45     Как ускорить данный алгоритм нахождения минимума на отрезке? #6
Просто отдельно записана подсказка.
Ну какая-то странная подсказка. Возможно, имеется в виду, что алгоритм должен быть не "в лоб". Но я такого не знаю.
К сожалению, я не знаю, как это сделать
C++
1
2
ofstream out("output.txt");
out << min;
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39
12.05.2014, 16:05  [ТС]     Как ускорить данный алгоритм нахождения минимума на отрезке? #7
Помогло использование scanf и printf вместо cin и cout. Спасибо за помощь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2014, 17:09     Как ускорить данный алгоритм нахождения минимума на отрезке?
Еще ссылки по теме:

Функция нахождения минимума и максимума в матрице C++
C++ Порядковые статистики. Алгоритм нахождения k-ого минимума в массиве
Функция нахождения минимума C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
12.05.2014, 17:09     Как ускорить данный алгоритм нахождения минимума на отрезке? #8
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;
}
Yandex
Объявления
12.05.2014, 17:09     Как ускорить данный алгоритм нахождения минимума на отрезке?
Ответ Создать тему
Опции темы

Текущее время: 16:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru