Подсчет операций укладки контейнеров роботов на C++ ⇐ C++

[Anonymous]

Я пытаюсь решить задачу, в которой робот укладывает контейнеры на складе, и хочу посчитать количество операций, которые он выполняет. Правила:

• Существует N контейнеров, расположенных в один ряд.
• Каждый контейнер имеет размер Ai (1 ≤ Ai ≤ M).
• Робот может выбрать контейнер и поместить его внутри большего контейнера справа от него.
• Контейнер, который уже содержит другой, нельзя использовать повторно.
• Мне нужно посчитать общее количество операций робота (вложений).

Ввод:

• Первая строка: два целых числа M (максимальный размер контейнера) и N (количество контейнеры).
• Вторая строка: N целых чисел A1, A2, ..., AN, обозначающих размеры контейнеров по порядку.

Вывод:

• Одно целое число: количество выполненных операций робота.

Пример ввода:

Код: Выделить всё

5 10
2 2 1 4 3 2 5 4 2 3

Пример вывода:

Код: Выделить всё

4

Объяснение:

• Робот вкладывает контейнеры в первый доступный контейнер большего размера справа от него.
• После выполнения 4 вложений больше контейнеров вкладывать невозможно.

Что я сделал Пробовал:
Я пробовал использовать вектор с Upper_bound и Lower_bound в обратном порядке:

Код: Выделить всё

for(auto it = arr.rbegin(); it != arr.rend();it++){
int val = *it;
auto idx = std::upper_bound(S.begin(), S.end(), val);
if (idx != S.end()) {
ops++;
S.erase(idx);
} else {
S.insert(std::lower_bound(S.begin(), S.end(), val), val);
}
}

Это работает для небольших примеров, но я не уверен, что это достаточно эффективно для больших N. Я также читал, что лучше использовать multiset. В настоящее время я получаю 5/100 с помощью этого решения.
Вопрос:

• Является ли этот подход правильным и эффективным?
• Как лучше всего реализовать это на C++ для обработки N до 20 000 и M до 1000?

Подробнее здесь: https://stackoverflow.com/questions/798 ... tions-in-c