Слишком много нот

@sssel · Регистрация: 30.08.2024

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

5. Слишком много нот
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Петя составил мелодию из n нот. Для простоты будем считать, что в один момент времени может
звучать только одна нота. Учитель по сольфеджио посмотрел на эту мелодию и сказал, что в ней
«Слишком много нот». Петя расстроился, но все же послушался. Теперь ему надо уменьшить число
различных используемых нот – для этого он хочет убрать все использования какой-то одной ноты,
а все остальные оставить на своих местах относительно друг друга.
Но Петя хочет, чтобы полученная мелодия была гармоничной, поэтому просит вас удалить все
вхождения одной ноты, чтобы получилась лексикографически наименьшая последовательность нот.
Помогите Пете!
Ноты представлены в виде натуральных чисел в диапазоне от 1 до n.
Последовательность чисел A лексикографически меньше последовательности B, если A является
началом B (например, (1, 2) < (1, 2, 3) или если первый различающийся элемент в A меньше, чем в
B (например, (1, 2) < (1, 3)).
Формат входных данных
В первой строке дано количество нот n (1 6 n 6 200000). В следующей строки записаны n нот
– последовательность чисел, каждое из которых лежит в диапазоне от 1 до n.
Формат выходных данных
Выведите лексикографически наименьшую последовательность нот, которую можно получить
удалением всех вхождений какой-то одной ноты.
Примеры
стандартный ввод стандартный вывод
2
2 2
5
1 2 1 2 1
1 1 1
5
4 5 5 3 4
4 3 4
Замечание
В первом примере можно удалить только двойку, тогда полученная последовательность будет
пуста.
Во втором примере если удалить 1, то будет (2, 2). А если удалить 2, то будет (1, 1, 1). Наименьшая
последовательность достигается при удалении двойки.
В третьем примере возможны варианты (5, 5, 3) при удалении четверки, (4, 3, 4) при удалении
пятерки и (4, 5, 5, 4) при удалении тройки. Из трех вариантов наименьшим будет (4, 3, 4).

Кто может решить эту задачy? У меня всегда превышено максимальное время работы))

@TheCalligrapher · 31.08.2024, 01:26

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

В первой строке дано количество нот n (1 6 n 6 200000).

"1 6 n 6 200000"?

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

Примеры
стандартный ввод стандартный вывод
2
2 2
5
1 2 1 2 1
1 1 1
5
4 5 5 3 4
4 3 4

Что здесь написано вообще? Где здесь что?

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

1. Пусть последовательность начинается с ноты a. Ищем то место в последовательности, где впервые встречается другая нота b: aa...ab...
2. Если a < b, то удалять a нельзя, обо оставшаяся последовательность будет заведомо больше того, что мы могли бы получить, сохранив a. В этом случае применяем тот же алгоритм, считая, что последовательность начинается с найденного места (с b) и далее.
3. Если a > b, то удаляем a. Конец работы.

(Для того, чтобы не обрабатывать конец последовательности как особый случай можно заранее добавить в ее конец ноту со значением 0.)

Другими словами, если я ничего не упустил, весь алгоритм сводится к тому, чтобы найти первое место в последовательности, где последующая нота меньше предыдущей. Удаляем предыдущую.

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
// C++20 для `std::erase`
#include <functional>
#include <algorithm>
#include <vector>
#include <iostream>
 
int main() 
{
  unsigned n = 0;
  std::cin >> n;
 
  std::vector<unsigned> notes(n);
  for (unsigned &note : notes)
    std::cin >> note;
 
  auto it = std::adjacent_find(notes.begin(), notes.end(), std::greater());
  if (it == notes.end())
    --it;
    
  std::erase(notes, +*it);
 
  for (unsigned note : notes)
    std::cout << note << " ";
  std::cout << std::endl;
}

@sporta1982 · 31.08.2024, 07:10

Задача удалить одну ноту.
в последовательности нота может встречаться несколько раз.
мы должны найти количество вхождений каждой ноты.
Удаляем.
Перебором мы получаем много последовательностей,
и дальше алгоритм по сравнению этих последовательностей.

@TheCalligrapher · 31.08.2024, 07:29

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

Перебором мы получаем много последовательностей,
и дальше алгоритм по сравнению этих последовательностей.

Рука-лицо... Читаем исходный вопрос:

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

У меня всегда превышено максимальное время работы))

Почему так получилось объяснять надо?

Как правильно решать эту задачу без "перебором мы получаем много последовательностей" я написал выше.

@sporta1982 · 31.08.2024, 07:30

ну как всегда я тупой

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. 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 существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@sssel 0 / 0 / 0 Регистрация: 30.08.2024 Сообщений: 1

	Слишком много нот 30.08.2024, 22:26. Показов 5863. Ответов 4 Метки нет (Все метки) 5. Слишком много нот Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Петя составил мелодию из n нот. Для простоты будем считать, что в один момент времени может звучать только одна нота. Учитель по сольфеджио посмотрел на эту мелодию и сказал, что в ней «Слишком много нот». Петя расстроился, но все же послушался. Теперь ему надо уменьшить число различных используемых нот – для этого он хочет убрать все использования какой-то одной ноты, а все остальные оставить на своих местах относительно друг друга. Но Петя хочет, чтобы полученная мелодия была гармоничной, поэтому просит вас удалить все вхождения одной ноты, чтобы получилась лексикографически наименьшая последовательность нот. Помогите Пете! Ноты представлены в виде натуральных чисел в диапазоне от 1 до n. Последовательность чисел A лексикографически меньше последовательности B, если A является началом B (например, (1, 2) < (1, 2, 3) или если первый различающийся элемент в A меньше, чем в B (например, (1, 2) < (1, 3)). Формат входных данных В первой строке дано количество нот n (1 6 n 6 200000). В следующей строки записаны n нот – последовательность чисел, каждое из которых лежит в диапазоне от 1 до n. Формат выходных данных Выведите лексикографически наименьшую последовательность нот, которую можно получить удалением всех вхождений какой-то одной ноты. Примеры стандартный ввод стандартный вывод 2 2 2 5 1 2 1 2 1 1 1 1 5 4 5 5 3 4 4 3 4 Замечание В первом примере можно удалить только двойку, тогда полученная последовательность будет пуста. Во втором примере если удалить 1, то будет (2, 2). А если удалить 2, то будет (1, 1, 1). Наименьшая последовательность достигается при удалении двойки. В третьем примере возможны варианты (5, 5, 3) при удалении четверки, (4, 3, 4) при удалении пятерки и (4, 5, 5, 4) при удалении тройки. Из трех вариантов наименьшим будет (4, 3, 4). Кто может решить эту задачy? У меня всегда превышено максимальное время работы)) 0

@sporta1982 213 / 59 / 7 Регистрация: 05.10.2023 Сообщений: 509
	31.08.2024, 07:10
	Задача удалить одну ноту. в последовательности нота может встречаться несколько раз. мы должны найти количество вхождений каждой ноты. Удаляем. Перебором мы получаем много последовательностей, и дальше алгоритм по сравнению этих последовательностей. 0

@sporta1982 213 / 59 / 7 Регистрация: 05.10.2023 Сообщений: 509
	31.08.2024, 07:30
	ну как всегда я тупой 0