Перлы — это мирная и первобытная раса, которая по вине человечества почти вымерла, а её…
- User
Перлы — это мирная и первобытная раса, которая по вине человечества почти вымерла, а её оставшиеся представители дрейфовали по космосу. Прибыв на Альфу перлы познакомились с Валерианом и Лорелин и смогли наконец-то обзавестись конвертером жемчужин.
Конвертер — миленький зверек, который производит жемчужины K различных цветов. Для запуска двигателя космического корабля перлам нужен набор из K различных по цвету жемчужин. Конвертер производит одну жемчужину в секунду. Для эффективной работы двигателя нужно, чтобы в каждом наборе для любой пары жемчужин выполнялось условие, что разница во времени между появлением этих жемчужин не превосходит M секунд. Каждая жемчужина может входить только в один набор.
Конвертер произвел N жемчужин и устал. Помогите перлам узнать, наибольшее возможное число наборов жемчужин, которые они смогут собрать из имеющихся жемчужин.
напиши программу на c++ вот пример ввод 6 2 3 1 2 2 1 3 3 вывод 1 4 3 5
- Assistant
Чтобы решить эту задачу, нужно разработать алгоритм, который будет находить наибольшее количество наборов жемчужин, соблюдая указанные условия. Вот пример реализации на C++:
#include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; int main() { int N, K, M; cin >> N >> K >> M; vector<int> pearls(N); for (int i = 0; i < N; ++i) { cin >> pearls[i]; } vector<vector<int>> sets; unordered_map<int, int> color_count; for (int i = 0; i < N; ++i) { color_count.clear(); int different_colors = 0; int start_index = i; for (int j = i; j < N && j < i + M; ++j) { if (color_count[pearls[j]] == 0) { different_colors++; } color_count[pearls[j]]++; if (different_colors == K) { vector<int> set; for (int k = i; k <= j; ++k) { set.push_back(k + 1); if (--color_count[pearls[k]] == 0) { different_colors--; } } sets.push_back(set); i = j; // Move i forward to j as this range is used break; } } } cout << sets.size() << endl; for (const auto& set : sets) { for (int index : set) { cout << index << " "; } cout << endl; } return 0; }Как работает программа:
-
Ввод данных: Мы считываем количество жемчужин
N, требуемое количество различных цветовKи максимальный допустимый промежуток времениM. -
Считывание цветов: В вектор
pearlsсохраняются цвета каждой изNжемчужин. -
Основная логика:
- Используем
unordered_mapcolor_countдля отслеживания количества каждого цвета в текущем рассматриваемом временном интервале. - Переменной
different_colorsхраним количество различных цветов в текущем временном окне. - Проходим по каждой жемчужине и расширяем окно длиной не более
M. - Когда находим
Kразличных цветов в допустимом окне, создаем набор и сохраняем его индексы в ответ.
- Используем
-
Вывод:
- Выводим количество найденных наборов.
- После этого выводим сами наборы, при этом индексы жемчужин увеличены на 1 для соответствия требуемому формату (индексация начинается с 1).
Таким образом, мы эффективно находим все наборы жемчужин, исходя из заданных условий.
-
- User
а можешь реализовать это на очередях?
- Assistant
Конечно! В данной задаче использование очередей (queues) может помочь эффективно управлять временными окнами и поддерживать актуальные множества цветов для формирования наборов. Давайте посмотрим, как можно использовать очередь для решения этой задачи.
#include <iostream> #include <vector> #include <unordered_map> #include <queue> using namespace std; int main() { int N, K, M; cin >> N >> K >> M; vector<int> pearls(N); for (int i = 0; i < N; ++i) { cin >> pearls[i]; } vector<vector<int>> sets; unordered_map<int, int> color_count; queue<int> window; for (int i = 0; i < N; ++i) { window.push(i); color_count[pearls[i]]++; while (window.size() > M) { int front = window.front(); window.pop(); color_count[pearls[front]]--; if (color_count[pearls[front]] == 0) { color_count.erase(pearls[front]); } } if (color_count.size() == K) { vector<int> current_set; while (!window.empty()) { int front = window.front(); window.pop(); current_set.push_back(front + 1); // +1 для 1-базовой индексации color_count[pearls[front]]--; if (color_count[pearls[front]] == 0) { color_count.erase(pearls[front]); } } sets.push_back(current_set); } } cout << sets.size() << endl; for (const auto& set : sets) { for (int index : set) { cout << index << " "; } cout << endl; } return 0; }Объяснение работы:
-
Ввод данных:
- Сначала читаем
N,K,Mи сами цвета жемчужин в массивpearls.
- Сначала читаем
-
Использование очереди:
- Очередь
windowбудет использоваться для хранения индексов текущих жемчужин, находящихся в рамках максимального допустимого времениM. unordered_mapcolor_countдля хранения количества каждого цвета в текущем окне.
- Очередь
-
Обработка жемчужин:
- Добавляем текущий индекс в очередь и инкрементируем количество для текущего цвета в
color_count. - Проверяем, если размер очереди превышает
M, удаляем передний элемент из очереди и уменьшаем количество его цвета. - Если у нас есть K различных цветов в окне, создаем новый набор жемчужин.
- Добавляем текущий индекс в очередь и инкрементируем количество для текущего цвета в
-
Вывод:
- Выводим количество наборов и каждый набор в отдельности, сохраняя индексы с 1.
Такое решение использует очередь для управления временными интервалами и удобно для задач, требующих ограничения по времени, как в данном случае.
-