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

@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 в твоем решении?

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

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

	Определить минимальное количество корректных отрезков, на которое можно разбить заданную последовательность. 24.07.2019, 22:31. Показов 9921. Ответов 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