Нужно сделать задачку

@Bluestick · Регистрация: 15.07.2019

Студворк — интернет-сервис помощи студентам

Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [1, 3, 2, 4] и [1, 2, 1, 2] являются корректными, а последовательность [1, 3, 2] — нет.

Задана последовательность [ a^1 , a^2 , ..., a^n ] . Будем называть отрезок элементов заданной последовательности [ a^l , a^l + 1 , ..., a r ] корректным, если он представляет собой корректную последовательность: a l является минимальным числом на этом отрезке, а a r — максимальным.
необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность [2, 3, 1, 1, 5, 1] можно разбить на три корректных отрезка: [2, 3] и [1, 1, 5] и [1] .

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

Входные данные
Первая строка входных данных содержит целое число n ( 1 ≤ n ≤ 300 000 ) — количество элементов в заданной последовательности.

Вторая строка содержит n целых чисел a^1 , a^2 , ..., a^n — заданную последовательность ( 1 ≤ a^i ≤ 10^9 ).

Выходные данные
Выведите одно число — минимальное количество корректных отрезков, на которое можно разбить заданную последовательность.

Примеры
входные данные
5
5 4 3 2 1
выходные данные
5
входные данные
4
1 3 2 4
выходные данные
1
входные данные
6
2 3 1 1 5 1
выходные данные
3

Можно не готовый код, а хотя бы алгоритм на практике

@dondublon · 30.07.2019, 14:16

Задача на динамическое программирование.

@Bluestick · 30.07.2019, 14:17 **[ТС]**

ну да, линейные алгоритмы быть точнее

@Ricoden · 30.07.2019, 16:04

dondublon, дп тут максимум 60 баллов получишь.

@dondublon · 30.07.2019, 16:32

Bluestick, не в курсе, что такое линейные алгоритмы, но вам виднее.

Ricoden, видимо, вы в курсе какого-то контекста этой задачи, но я - нет. Я не знаю, на сколько баллов она оценивается, 60 - это хорошо или плохо, да мне это и неинтересно.
Если это намёк, что данную задачу можно решить каким-то другим способом - поделитесь, это уже интересно.

Добавлено через 2 минуты
Bluestick, посмотрел в инете. Линейные алгоритмы - прямые, как линия партии, без единого if-а. Удивлюсь, если они вам тут помогут.

@Ricoden · 30.07.2019, 16:34

dondublon, он прав, просто эта задача по спортивному программированию из раздела "Линейные алгоритмы". Нужно придумать решение за O(n).

@Bluestick · 30.07.2019, 16:40 **[ТС]**

можно находить минимум на
отрезке с помощью дерева отрезков или
разреженных таблиц.
O(n) отрезков, обработка каждого за O(log n) или
O(1).
Вот только я не знаю как бы это реализовать

@dondublon · 31.07.2019, 10:48

Bluestick, ну что, как успехи? Про ДП прочитали? Не думаю, что тут нужно дерево отрезков.

@Green_Angel · 31.07.2019, 18:35

Попробуйте.

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 <iostream>
#include <vector>
#include <cassert>
 
using namespace std;
 
struct Pair {
    int value;
 
    int pos;
};
 
int main() 
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> nextLessPos(n);
    {
        vector<Pair> stack;
        stack.push_back(Pair{ 0, n });
        for (int i = n - 1; i >= 0; i--) {
            assert(!stack.empty());
            while (stack.back().value >= a[i]) {
                stack.pop_back();
                assert(!stack.empty());
            }
            assert(!stack.empty());
            assert(stack.back().value < a[i]);
            nextLessPos[i] = stack.back().pos;
            stack.push_back(Pair{a[i], i});
        }
    }
 
    vector<int> nextGEPos(n);
    {
        vector<Pair> stack;
        stack.push_back(Pair{ 1000*1000*1000, n });
        for (int i = n - 1; i >= 0; i--) {
            assert(!stack.empty());
            while (stack.back().value < a[i]) {
                stack.pop_back();
                assert(!stack.empty());
            }
            assert(!stack.empty());
            assert(stack.back().value >= a[i]);
            nextGEPos[i] = stack.back().pos;
            stack.push_back(Pair{ a[i], i });
        }
    }
 
    int count = 0;
    for (int pos = 0; pos < n; ) {
        int lessPos = nextLessPos[pos];
        assert(lessPos > pos);
        int gePos = pos;
        while (nextGEPos[gePos] < lessPos) {
            gePos = nextGEPos[gePos];
        }
        pos = gePos + 1;
        count++;
    }
    cout << count;
}

@tooru · 31.07.2019, 20:08

Python
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
def main() :
    n = int(input())
    a = [int(input()) for _ in range(n)]
 
    nextLessPos = [0] * n
 
    stack = []
    stack.append(( 0, n ))
    for i in range(n - 1, -1, -1):
        assert len(stack) > 0
        while stack[-1][0] >= a[i]:
            stack.pop()
            assert len(stack) > 0
        assert len(stack) > 0
        assert stack[-1][0] < a[i]
        nextLessPos[i] = stack[-1][1]
        stack.append((a[i], i))
 
    nextGEPos = [0] * n
    
    stack = []
    stack.append((1000*1000*1000, n))
    for i in range(n - 1, -1, -1):
        assert len(stack) > 0
        while stack[-1][0] < a[i]:
            stack.pop()
            assert len(stack) > 0
        assert len(stack) > 0
        assert stack[-1][0] >= a[i]
        nextGEPos[i] = stack[-1][1]
        stack.append((a[i], i))
    
    count = 0
    pos = 0
    while pos  < n:
        lessPos = nextLessPos[pos]
        assert lessPos > pos
        gePos = pos
        while nextGEPos[gePos] < lessPos:
            gePos = nextGEPos[gePos]
        pos = gePos + 1
        count += 1
    print(count)
 
if __name__ == '__main__':
    main()

@_Miximka_ · 01.08.2019, 08:38

Ну эта задача со ВсеРоса. И там ДО заходит)))

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69

	Нужно сделать задачку 30.07.2019, 14:09. Показов 1311. Ответов 10 Метки нет (Все метки) Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [1, 3, 2, 4] и [1, 2, 1, 2] являются корректными, а последовательность [1, 3, 2] — нет. Задана последовательность [ a^1 , a^2 , ..., a^n ] . Будем называть отрезок элементов заданной последовательности [ a^l , a^l + 1 , ..., a r ] корректным, если он представляет собой корректную последовательность: a l является минимальным числом на этом отрезке, а a r — максимальным. необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность [2, 3, 1, 1, 5, 1] можно разбить на три корректных отрезка: [2, 3] и [1, 1, 5] и [1] . Требуется написать программу, которая по заданной последовательности определяет, на какое минимальное количество корректных отрезков её можно разбить. Входные данные Первая строка входных данных содержит целое число n ( 1 ≤ n ≤ 300 000 ) — количество элементов в заданной последовательности. Вторая строка содержит n целых чисел a^1 , a^2 , ..., a^n — заданную последовательность ( 1 ≤ a^i ≤ 10^9 ). Выходные данные Выведите одно число — минимальное количество корректных отрезков, на которое можно разбить заданную последовательность. Примеры входные данные 5 5 4 3 2 1 выходные данные 5 входные данные 4 1 3 2 4 выходные данные 1 входные данные 6 2 3 1 1 5 1 выходные данные 3 Можно не готовый код, а хотя бы алгоритм на практике 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	30.07.2019, 14:16
	Задача на динамическое программирование. 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 14:17 [ТС]
	ну да, линейные алгоритмы быть точнее 0

@Ricoden 2 / 3 / 0 Регистрация: 28.07.2014 Сообщений: 12
	30.07.2019, 16:04
	dondublon, дп тут максимум 60 баллов получишь. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	30.07.2019, 16:32
	Bluestick, не в курсе, что такое линейные алгоритмы, но вам виднее. Ricoden, видимо, вы в курсе какого-то контекста этой задачи, но я - нет. Я не знаю, на сколько баллов она оценивается, 60 - это хорошо или плохо, да мне это и неинтересно. Если это намёк, что данную задачу можно решить каким-то другим способом - поделитесь, это уже интересно. Добавлено через 2 минуты Bluestick, посмотрел в инете. Линейные алгоритмы - прямые, как линия партии, без единого if-а. Удивлюсь, если они вам тут помогут. 0

@Ricoden 2 / 3 / 0 Регистрация: 28.07.2014 Сообщений: 12
	30.07.2019, 16:34
	dondublon, он прав, просто эта задача по спортивному программированию из раздела "Линейные алгоритмы". Нужно придумать решение за O(n). 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 16:40 [ТС]
	можно находить минимум на отрезке с помощью дерева отрезков или разреженных таблиц. O(n) отрезков, обработка каждого за O(log n) или O(1). Вот только я не знаю как бы это реализовать 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	31.07.2019, 10:48
	Bluestick, ну что, как успехи? Про ДП прочитали? Не думаю, что тут нужно дерево отрезков. 0

@_Miximka_ 0 / 0 / 0 Регистрация: 01.01.2019 Сообщений: 2
	01.08.2019, 08:38
	Ну эта задача со ВсеРоса. И там ДО заходит))) 0