Форум программистов, компьютерный форум 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, сделал зависимости нажатия кнопочек от того что происходит на экране, ну то есть если уровень здоровья маленький, то программа нажимает кнопочку 1 и т.д. Реализовал это через гетпиксель, обращаюсь к координатам, сверяю пикселя. Но столкнулся с проблемой, что когда запускаю прогу на ноуте, все отлично работает, но когда...
Какой фигурой обозначаются в блок схеме C++
Какой фигурой обозначаются в блок схеме запись в файл/чтение из файла? к примеру: для fout.open("input.txt");? fout <<...;?
C++ Создание класса с указателем http://www.cyberforum.ru/cpp-beginners/thread1172975.html
Всем привет :) Есть такая часть задания: Нужно создать класс АВТОМОБИЛЬ, который имеет марку (указатель на строку), цвет, объем двигателя, мощность. public class Automobile { public CarBrand Brand { get; set; } public Color Color { get; set; } public Double EngineVolume { get; set; } public Double EngineCapacity { get; set; }
C++ Как считать символ два раза char ch = ' '; cin.get(ch); нужно первый раз считать символ функцией-членом .get() которая не пропускает разделители, для того, что бы выловить переход на новую строку функцией isspace(ch); второй раз считать cin>>ch; что бы разделители не учитывались, и программа работала корректно!\ Или, подскажите такую функцию, что бы ловила только нажатие Enter, что бы , если это не... подробнее

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

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

Рассмотрим последовательность целых чисел длины 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru