Задача на два указателя
Я знаю, что на форуме эта задача уже была, но хочу сам решить эту задачу. Очень прошу, помогите!
Красота превыше всего
В парке города Питсбурга есть чудесная аллея, состоящая из 𝑁 посаженных в один ряд деревьев, каждое одного из 𝐾 сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из 𝐾 видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
Входные данные
В первой строке находятся два числа 𝑁 и 𝐾 (1⩽𝑁,𝐾⩽250000). Во второй строке следуют 𝑁 чисел (разделённых пробелами), 𝑖-е число второй строки задаёт вид 𝑖-го слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого вид.
Выходные данные
Выведите два числа: координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите самый левый из отрезков.
Примеры
Ввод
Вывод
5 3
1 2 1 3 2
2 4
6 4
2 4 2 3 3 1
2 6
Мой код:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
if (k == 1) cout << "1 1";
vector<int> a(n);
vector<int> b(k); // вектор, который будет считать кол-во разных видов в срезе
for (int i = 0; i < n; ++i) cin >> a[i];
int ibest = -1, jbest = -1, min_size = n + 1;
for (int i = 0; i < k; ++i) b[a[i] - 1] += 1;
for (int i = 0, j = k - 1; min_size != k && i < n && j < n;)
{
if (find(b.begin(), b.end(), 0) != b.end()) // если в срезе нет какого-то из видов, то добавляем правый
{
++j;
b[a[j] - 1] += 1;
}
if (b[a[i] - 1] > 1) // если в срезе несколько одинаковых видов, то убираем i-ый элемент
{
b[a[i] - 1] -= 1;
++i;
}
if (i == ibest && j == jbest) break; // чтобы не было зацикливания в случае, если j = n - 1
if (find(b.begin(), b.end(), 0) == b.end() && j - i + 1 < min_size) // если все виды есть и размер меньше минимального, то перезаписываем
{
ibest = i;
jbest = j;
min_size = j - i + 1;
}
}
cout << ibest + 1 << " " << jbest + 1;
return 0;
}
Очень прошу исправить мой код!!
Для решения задачи на два указателя, где необходимо найти минимальный подотрезок, содержащий хотя бы по одному дереву каждого сорта, можно использовать метод двух указателей. Этот метод позволяет эффективно находить нужный подотрезок, двигая указатели по массиву. Ваша текущая реализация содержит несколько ошибок, которые можно исправить следующим образом:
1. Инициализация и проверка условий: Убедитесь, что вы правильно инициализируете и проверяете условия для указателей и массива подсчета.
2. Использование двух указателей: Начните с обоими указателями в начале массива. Двигайте правый указатель, чтобы включить все виды деревьев. Как только все виды включены, двигайте левый указатель, чтобы минимизировать длину подотрезка.
3. Обновление минимальной длины: Обновляйте минимальную длину подотрезка каждый раз, когда все виды деревьев включены.
Вот исправленный код:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
unordered_map<int, int> count;
int num_types = 0;
int left = 0, right = 0;
int min_length = n + 1;
int best_left = 0, best_right = 0;
while (right < n) {
// Добавляем дерево в подотрезок
if (count[a[right]] == 0) {
num_types++;
}
count[a[right]]++;
// Если все виды присутствуют, пробуем сократить подотрезок
while (num_types == k) {
if (right - left + 1 < min_length) {
min_length = right - left + 1;
best_left = left;
best_right = right;
}
// Убираем дерево из подотрезка
count[a[left]]--;
if (count[a[left]] == 0) {
num_types--;
}
left++;
}
right++;
}
cout << best_left + 1 << " " << best_right + 1;
return 0;
}
Объяснение изменений:
- unordered_map: Используется для подсчета количества деревьев каждого вида в текущем подотрезке.
- num_types: Переменная для отслеживания количества различных видов деревьев в подотрезке.
- Циклы: Внешний цикл увеличивает правый указатель, внутренний цикл уменьшает левый указатель, чтобы минимизировать длину подотрезка.
Этот код должен корректно находить минимальный подотрезок, содержащий все виды деревьев, и выводить его границы.
[1] https:/апо.рф/%D0%BC%D0%B0%D1%82%D0%B5%D1%80%D0%B8%D0%B0%D0%BB%D1%8B/%D0%BC%D0%B5%D1%82%D0%BE%D0%B4-%D0%B4%D0%B2%D1%83%D1%85-%D1%83%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D0%B5%D0%B9/
[2] https:/www.youtube.com/watch?v=LgpiMr38jg0
[3] https://ru.stackoverflow.com/questions/1499238/Как-можно-оптимизировать-код-в-данной-задаче-Не-проходит-по-времени-использую
[4] https:/silvertests.ru/GuideView.aspx?id=30837
[5] https:/krilovskiy.com/posts/algo-patterns-fast-slow-pointer/
[6] https:/codeforces.com/blog/entry/4136?locale=ru
[7] https:/www.youtube.com/watch?v=MyWNZJ10zIU
// ввод
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &v : a) { cin >> v; }
multiset<int> p; // деревья в границах отрезка
set<int> q; // виды деревьев в границах отрезка
int min_l = 1, min_r = n; // границы минимального отрезка
// пока правая граница отрезка не достигла конца аллеи
for (int l = 0, r = 0; r < n;) {
// двигаем правую границу, пока в отрезке ещё не все виды
for(; r < n && q.size() < k; ++r) {
p.insert(a[r]);
q.insert(a[r]);
}
// двигаем левую границу, пока в отрезке все виды
for(; q.size() == k; ++l) {
p.erase(p.find(a[l]));
if (!p.contains(a[l])) { q.erase(a[l]); }
}
// выбираем меньший отрезок
if (r - l < min_r - min_l) {
min_l = l;
min_r = r;
}
}
// вывод
cout << min_l << ' ' << min_r; Реализация на множествах: set содержит только уникальные значения, multiset - все добавляемые значения.
Рабочий код: https://onlinegdb.com/hJ9rOPEsO