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

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

Новые блоги и статьи Все статьи Все блоги /
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

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

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

Опции темы