Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
1 / 1 / 0
Регистрация: 25.10.2021
Сообщений: 87

Оптимизация программы(Размер окна)

18.05.2022, 21:43. Показов 1076. Ответов 2

Студворк — интернет-сервис помощи студентам
Может кто помочь в оптимизации кода, мой код, который предоставил не проходит по времени.

Для данного массива чисел A[1 .. n] найти максимум в каждом окне размера m .
Наивный способ решить данную задачу - честно просканировать каждое окно и найти в нем максимум. Время работы такого алгоритма - O(nm). Ваша задача реализовать алгоритм со временем работы O(n).

Формат ввода
Массив чисел A[1 .. n] и число 1 <= m <= n.
Ограничения.
1 <= n <= 105, 1 <= m <= n, 0 <= A[i] <= 105 для всех 1 <= i <= n.

Формат вывода
Максимум подмассива A[i .. i+m+1] для всех 1 <= i <= n-m+1.

Пример 1
Ввод
8
2 7 3 1 5 2 6 2
4
Вывод
7 7 5 6 6

Пример 2
Ввод
3
2 1 5
1
Вывод
2 1 5

Вот мой код:
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
#include <iostream>
#include <fstream>
using namespace std;
ifstream vvod("input.txt"); ofstream vivod("output.txt");
int* Massiv, n, k;
void Maximum(int massiv[], int n, int k);
int main() 
{  
    vvod >> n; 
    Massiv = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) vvod >> Massiv[i];
    vvod >> k; 
    Maximum(Massiv, n, k);
    if (n) free(Massiv);
    return 0;
}
void Maximum(int massiv[], int n, int k)
{
    int max_raz;
    for (int i = 0; i <= n - k; ++i)
    {
        max_raz = massiv[i];
        for (int j = 1; j < k; ++j)
        {
            if (massiv[i + j] > max_raz)
                max_raz = massiv[i + j];
        }
        vivod << max_raz << " ";
    }
}
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.05.2022, 21:43
Ответы с готовыми решениями:

Как соотнести размер картинки и окна программы в visual studio
Привет всем. Просьба не переносить, пожалуйста, тему в другой раздел. Есть картинка предположим 500x300px (ИСП. Пиксели). Есть...

Не вижу окна с кодом (нет окна редактирования): найти причины странного поведения программы
Создаю проект, а кроме синего экрана ничего больше нет, не знаю, что делать. Прочла здесь же про образователь решений(типа должен быть...

Размер окна программы
Есть программа с окном 1280х720 (1-ая картинка ) и есть монитор с разрешением 1280х480. При компиляции программа в таком мониторе...

2
Нарушающий
417 / 305 / 46
Регистрация: 13.04.2022
Сообщений: 1,759
18.05.2022, 23:52
Создай отсортированный список чисел в текущем окне. Верхнее число - это максимум всех чисел в окне.
При шаге вправо выкинь ушедшее число и добавь новое, сохраняя порядок сортировки (как в сортировке вставкой). Сверху снова будет максимум всех чисел в окне.

О((n-m)*log(m)) для эффективной вставки
0
 Аватар для igorrr37
2870 / 2017 / 991
Регистрация: 21.12.2010
Сообщений: 3,728
Записей в блоге: 15
19.05.2022, 08:24
Лучший ответ Сообщение было отмечено kuzhimoshi как решение

Решение

через дерево отрезков
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
52
53
54
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <functional>
 
 
int main()
{
    std::stringstream ss
    {
        "8\n"
        "2 7 3 1 5 2 6 2\n"
        "4"
    };
    int n{}, m{};
    ss >> n;
    std::vector<int> vct(n); // массив
    for (int i = 0; i < n; ++i)
    {
        ss >> vct[i];
    }
    ss >> m;
    std::vector<int> vt(4 * n); // дерево отрезков
 
    std::function<void(int, int, int)> build = [&vt, &build, &vct](int ind, int tl, int tr) // построение дерева отрезков (при вызове извне первые три аргумента: 1, 0, n-1)
    {
        if (tl == tr)
            vt[ind] = vct[tl];
        else 
        {
            int tm = (tl + tr) / 2;
            build(ind * 2, tl, tm);
            build(ind * 2 + 1, tm + 1, tr);
            vt[ind] = std::max(vt[ind * 2], vt[ind * 2 + 1]);
        }
    };
    build(1, 0, n - 1);
 
    std::function<int(int, int, int, int, int)> max = [&vt, &max](int ind, int tl, int tr, int l, int r) // запрос максимума на отрезке [l, r] включительно (при вызове извне первые три аргумента: 1, 0, n-1)
    {
        if (l > r)
            return 0;
        if (l == tl && r == tr)
            return vt[ind];
        int tm = (tl + tr) / 2;
        return std::max(max(ind * 2, tl, tm, l, std::min(r, tm)), max(ind * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r));
    };
 
    for (int i = 0; i < n - m + 1; ++i)
    {
        std::cout << max(1, 0, n - 1, i, i+m-1) << " ";
    }
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.05.2022, 08:24
Помогаю со студенческими работами здесь

Размер окна программы
когда ставлю AutoSize-true то все слишком приближенно к границам окна, при true значения ClientHeight и ClientWidht изменить нельзя....

Подстроить размер окна относительно размера другого окна в X11
Есть два риложения, у обоих устанавливается атрибут WA_X11NetWmWindowTypeaDock. Сначала запускается первое приложение и занимает какое-то...

Может ли оконная процедура различить, изменён ли размер окна функцией MoveWindow, или мышью за рамку окна?
Стиль WS_BORDER | WS_SIZEBOX | WS_CHILDWINDOW | WS_CLIPSIBLINGS | WS_THICKFRAME | WS_VISIBLE.

Какой приблизительно размер добавляемого компонента и влияет ли он на размер самой программы
Здравствуйте, меня интересует вопрос, когда создаешь какой нить компонент, какой приблизительно его размер и влияет ли он на размер самой...

Создание невидимого окна поверх окна другой программы
Здравствуйте, как сделать невидимое окно поверх окна сторонней программы , например блокнота, и если изменился размер блокнота то и окно...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru