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

@Skybi · Регистрация: 28.09.2018

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

Известно, что если сохранить в каждом слове текста первую и последнюю букву, а остальные переставить произвольным образом, получившийся текст по-прежнему можно достаточно свободно прочитать. В лаборатории информатики исследуют аналогичный феномен для числовых последовательностей.

Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [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
Не обязательно писать сам код, можно просто написать алгортим решения, или может метод спомощью которого решается

@Ricoden · 30.07.2019, 15:43

Bluestick, если программа набирает 60 баллов - это не значит, что "коды не работают", а вполне приемлемый результат. Хочешь получить 100, оптимизируй или предложи свой алгоритм.

@Bluestick · 30.07.2019, 15:46

ну и к чему это было? Я захотел узнать почему она выбрала их 'решение', а не 'почему она выбирает решение? почему не я?'

Добавлено через 1 минуту

Сообщение от Ricoden

если программа набирает 60 баллов - это не значит, что "коды не работают", а вполне приемлемый результат. Хочешь получить 100, оптимизируй или предложи свой алгоритм.

Стоп они работают? У меня почему то не компилируется (на тестах тоже 0 баллов)

@Ricoden · 30.07.2019, 15:46

Bluestick, потому что решение выбирает автор темы или модер.

Да, отмеченный код рабочий.

@Bluestick · 30.07.2019, 15:54

вы уверены? Я никак не изменял код, запустил на тесты и в начале пишет 'неверный ответ' а все остальные тесты 'пропущено' или наоборот надо чуть изменить код?

@Ricoden · 30.07.2019, 16:00

Вот, попробуйте.

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
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
int split(uint32_t* begin, uint32_t* end) {
    size_t cnt = 0;
    uint32_t *it1, *it2;
    for (it1 = it2 = begin; it2 != end; ++it1) {
        if (it1 == end || *it1 < *begin) {
            begin = it1 = ++it2;
            ++cnt;
        }
        else if (*it1 >= *it2) {
            it2 = it1;
        }
    }
    return cnt;
}
 
int main() {
    size_t  n;
    cin >> n;
 
    uint32_t *arr = new uint32_t[n];
    for (int i=0;i<n;i++)
        cin>>arr[i];
        
    cout<<split(arr, arr+n);
 
    return 0;
}

@Bluestick · 30.07.2019, 16:02

Огромное спасибо

@qMaxi · 30.07.2019, 18:22

Кто - нибудь решил эту задачу на 100? Я пытался оптимизировать свой алгоритм по http://vos.olimpiada.ru/upload... l-17-8.pdf (слайд 114), но как - то не получается(

@Who_is_the_coon · 31.07.2019, 21:15

SkyBi,Не обьяснишь что обозначает cek в твоем решении?

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

@Skybi 2 / 2 / 0 Регистрация: 28.09.2018 Сообщений: 18

	Определить минимальное количество корректных отрезков, на которое можно разбить заданную последовательность. 24.07.2019, 22:31. Показов 10284. Ответов 27 Метки нет (Все метки) Известно, что если сохранить в каждом слове текста первую и последнюю букву, а остальные переставить произвольным образом, получившийся текст по-прежнему можно достаточно свободно прочитать. В лаборатории информатики исследуют аналогичный феномен для числовых последовательностей. Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [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

@Ricoden 2 / 3 / 0 Регистрация: 28.07.2014 Сообщений: 12
	30.07.2019, 15:43
	Bluestick, если программа набирает 60 баллов - это не значит, что "коды не работают", а вполне приемлемый результат. Хочешь получить 100, оптимизируй или предложи свой алгоритм. 0

@Ricoden 2 / 3 / 0 Регистрация: 28.07.2014 Сообщений: 12
	30.07.2019, 15:46
	Bluestick, потому что решение выбирает автор темы или модер. Да, отмеченный код рабочий. 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 15:54
	вы уверены? Я никак не изменял код, запустил на тесты и в начале пишет 'неверный ответ' а все остальные тесты 'пропущено' или наоборот надо чуть изменить код? 0

@Bluestick 0 / 0 / 0 Регистрация: 15.07.2019 Сообщений: 69
	30.07.2019, 16:02
	Огромное спасибо 0

@qMaxi 0 / 0 / 0 Регистрация: 30.07.2019 Сообщений: 1
	30.07.2019, 18:22
	Кто - нибудь решил эту задачу на 100? Я пытался оптимизировать свой алгоритм по http://vos.olimpiada.ru/upload... l-17-8.pdf (слайд 114), но как - то не получается( 0

@Who_is_the_coon 0 / 0 / 0 Регистрация: 31.07.2019 Сообщений: 1
	31.07.2019, 21:15
	SkyBi,Не обьяснишь что обозначает cek в твоем решении? 0