Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
Pepsy
47 / 32 / 9
Регистрация: 05.01.2013
Сообщений: 307
1

Для каждых k подряд идущих чисел найти минимум

13.11.2014, 20:06. Просмотров 658. Ответов 6
Метки нет (Все метки)

Дано n чисел. Для каждых k подряд идущих чисел найти минимальное среди них.
Вся соль задачи в том, что 1 ≤ n ≤ 150000, 1 ≤ k ≤ 10000, k ≤ n
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2014, 20:06
Ответы с готовыми решениями:

Найти суммы каждой пары подряд идущих чисел
Люди, срочно нужно написать програмку. Завтра сдавать. Дана последовательность...

Найти максимальное количество простых чисел, идущих подряд
В последовательности целых чисел найти максимальное количество простых чисел,...

Найти в последовательности чисел два подряд идущих нуля
Дана последовательность из n чисел найти в ней кол-во 2 подряд идущих 0 Нужно...

Разработать функцию, определяющую, есть ли в строке S как минимум 5 подряд идущих латинских букв
Разработать функцию Is5Latin(const S:string):boolean, определяющую, есть ли в...

Программа для нахождения к-ой цифры в ряду подряд идущих натуральных чисел.
Найти k-ую цифру в ряду цифр, составленных из подряд идущих натуральных чисел,...

6
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
13.11.2014, 20:52 2
Куча, например, или дерево отрезков или (как мне кажется проще всего, если получится) дерево Фенвика.

Добавлено через 18 минут
У меня такая штука получилась. Кажется, работает
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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#include <list>
 
using namespace std;
 
const int INFINITY = 1 << 30;
const int MAX_NUMBERS = 150000;
int numbers[MAX_NUMBERS + 1], arr[MAX_NUMBERS + 1];
int n, k;
 
int Next(int x)
{
    return x | (x+1);
}
 
int Prev(int x)
{
    return (x & (x+1)) - 1;
}
 
 
void Modify(int x, int y)
{
    while(x <= n)
    {
        arr[x] = min(arr[x], y);
        x = Next(x);
    }
}
 
 
int FindMin(int r)
{
    int ans = INFINITY;
    while(r > 0)
    {
        ans = min(ans, arr[r]);
        r = Prev(r);
    }
    return ans;
}
 
 
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &numbers[i]);
        arr[i] = INFINITY;
    }
    list<int> answer;
    for(int i = n - k + 1; i <= n; ++i)
        Modify(i, numbers[i]);
    for(int i = n - k + 1; i > 0; --i)
    {
        answer.push_front(FindMin(i + k - 1));
        if(i > 1)
            Modify(i - 1, numbers[i - 1]);
    }
 
    for(auto& it: answer)
        printf("%d ", it);
 
    return 0;
}
1
Pepsy
47 / 32 / 9
Регистрация: 05.01.2013
Сообщений: 307
13.11.2014, 23:32  [ТС] 3
Dani, а можно какую-то ссылочку, где бы с этим можно было ознакомиться?

Не по теме:

а то в педивикии не оч...

0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
14.11.2014, 16:03 4
http://e-maxx.ru/algo/fenwick_tree
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
14.11.2014, 16:56 5
Dani, чет кажись проще всего с сетом или приорити кью. если не знать ДО и фенвика.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
14.11.2014, 16:59 6
Приорити кью врядли, т.к. при сдвиге отрезка нужно как-то вычислить число, которого теперь в отрезке не будет и удалить его. А вот сетом - можно.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
14.11.2014, 17:03 7
Dani, а да тупанул.
0
14.11.2014, 17:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.11.2014, 17:03

Определить, имеются ли в заданной последовательности 4 подряд идущих числа, кратных 7; найти сумму таких чисел
Здравствуйте. Напишите, пожалуйста, код для этого задания (желательно с...

Найти количество N-значных чисел, состоящих из цифр 1 и 2, не содержащих три подряд идущих одинаковых цифры
Здравствуйте! Вот еще одна задача с E-olymp (№ 12). К сожалению, только 67%...

Дана последовательность из N вещественных чисел. Первое число в последовательности нечетное. Найти сумму всех идущих подряд в начале последовательност
Дана последовательность из N вещественных чисел. Первое число в...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru