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

Как ускорить данный алгоритм нахождения минимума на отрезке? - 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); ... подробнее

Показать сообщение отдельно
firefox123
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 39

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

12.05.2014, 11:18. Просмотров 736. Ответов 7
Метки (Все метки)

Здравствуйте, подскажите, пожалуйста, почему решение не проходит по времени на нескольких тестах? Как исправить это?

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

Рассмотрим последовательность целых чисел длины 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru