Жадный алгоритм создания возрастающих последовательностей

Question

Дан массив cube целых чисел размера n (1 ≤ n ≤ 2,5 * 10^5). Нужно каждому элементу массива присвоить цвет (натуральное число) так, чтобы элементы с одинаковым цветом были строго возрастающей последовательностью. Вывести наименьшее количество требуемых цветов (m) и цвет каждого элемента.
Входные данные:

10
2 3 1 3 2 1 2 2 4 3

Выходные данные:

5
1 1 2 2 3 4 4 5 2 5

Входные данные:

10
3 1 4 1 5 9 2 6 5 3

Выходные данные:

4
1 2 1 3 1 1 3 3 2 4

Предполагается нахождение ближайшего левого минимума для каждого числа. st - стек индексов, которым нужно найти левый минимум. Но код даёт WA даже на первом тесте. При i = 6 стек состоит из 2 и 3, то есть st.top() == 2, поэтому по сути cube[i] (т.е 2) нельзя присвоить цвет. Но данный код не учитывает 3 в начале стека, т.е 2 и 3 можно присвоить один цвет:

#include <iostream>
#include <vector>
#include <stack>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> cube(n), res(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> cube[i];
    }
    int m = 0;
    std::stack<int> st;
    for (int i = n - 1; i > -1; --i) {
        if (st.empty() || cube[i] >= cube[st.top()]) {
            ++m;
            res[i] = m;
        } else {
            res[i] = res[st.top()];
            st.pop();
        }
        st.push(i);
    }
    std::cout << m << std::endl;
    for (int color : res) {
        std::cout << color << ' ';
    }
}

Чтобы исправить это, я заменил стек на вектор (потеряв скорость), для проверки всего стека на возможность иметь одинаковый цвет с cube[i]. Данный вариант даёт WA на 5 тесте, например, для:

10
6 6 1 7 5 6 1 9 8 3

m должно быть 4, а не 5:

std::vector<int> st;
size_t j;
for (int i = n - 1; i > -1; --i) {
    j = 0;
    while (j < st.size() && cube[i] >= cube[st[j]]) {
        ++j;
    }
    if (st.empty() || j == st.size()) {
        ++m;
        res[i] = m;
    } else {
        res[i] = res[st[j]];
        st.erase(st.begin() + j);
    }
    st.push_back(i);
}

Также я пробовал вариант за O(n^2), но TE на 14 тесте:

int m = 0;
for (int i = 0; i < n; ++i) {
    if (res[i] == 0) {
        ++m;
        res[i] = m;
        int mx = cube[i];
        for (int j = i + 1; j < n; ++j) {
            if (cube[j] > mx && res[j] == 0) {
                mx = cube[j];
                res[j] = m;
            }
        }
    }
}

Answer 1

Стека недостаточно для решения этой задачи. Тут нужны несколько идей.

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

В данном случае хорошо подойдёт std::set Сложность O(N) по памяти, O(N log N) по времени работы, должно успевать по времени.

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

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int ans[300000];

int main() {
    int N;
    cin >> N;
    set<pair<int, int>> s; 
    int count = 0;
    for (int i=0; i < N; i++) {
        int a;
        cin >> a;
        auto it = s.lower_bound(make_pair(a,-1)); 
        if (it == s.begin()) {
            ans[i] = ++count;
        } else {
            it--;
            ans[i] = ans[it->second];
            s.erase(*it);
        }
        s.insert(make_pair(a,i));
    }
    cout << count << endl;
    for (int i=0; i < N; i++)
        cout << ans[i]<<" ";
    cout << endl;
    return 0;
}

БЛОГ НА HUSL

Жадный алгоритм создания возрастающих последовательностей

Ответы (1 шт):