Разбор задачи «Кодирование длин серий»

1. Идея

Нужно пройти по массиву слева направо и разбить его на максимальные подряд идущие группы одинаковых чисел.

Для каждой такой группы требуется вывести два числа:

• значение элемента;
• длину серии.

Это и есть обычное кодирование длин серий: вместо повторяющихся элементов храним одно значение и количество его повторений подряд.

2. Наблюдения

1. Серия заканчивается в тот момент, когда следующий элемент отличается от текущего.
2. Значит, достаточно хранить:
   • current_value — значение текущей серии;
   • current_count — сколько раз оно встретилось подряд.
3. Если очередной элемент равен current_value, просто увеличиваем current_count.
4. Если не равен, значит серия завершилась:
   • сохраняем пару current_value current_count;
   • начинаем новую серию с текущего элемента.
5. После окончания прохода нужно не забыть добавить последнюю серию, потому что она не будет закрыта внутри цикла автоматически.

3. Алгоритм

1. Считываем n и массив a.
2. Создаём список ответа.
3. Инициализируем текущую серию:
   • current_value = a[0]
   • current_count = 1
4. Для каждого элемента начиная со второго:
   • если он равен current_value, увеличиваем current_count;
   • иначе:
     • добавляем в ответ current_value и current_count;
     • начинаем новую серию.
5. После цикла добавляем последнюю серию в ответ.
6. Выводим все числа ответа через пробел.

4. Почему это работает

Рассмотрим, что происходит во время прохода по массиву.

На каждом шаге переменные current_value и current_count описывают текущую незавершённую серию одинаковых элементов, которая заканчивается на текущей позиции.

Есть два случая:

1. a[i] == current_value
   Тогда серия продолжается, и нужно только увеличить её длину.

2. a[i] != current_value
   Тогда предыдущая серия уже точно завершилась на элементе i - 1.
   Значит, её можно безопасно записать в ответ. После этого начинается новая серия из элемента a[i].

Так мы последовательно обрабатываем все серии ровно по одному разу и записываем для каждой правильную пару: значение и длину.

Остаётся только последняя серия: после завершения цикла она ещё не была добавлена, поэтому мы дописываем её отдельно.

Следовательно, алгоритм корректно строит RLE-представление всей последовательности.

5. Сложность

• Время: O(n), потому что массив просматривается один раз.
• Память: O(n) в худшем случае на хранение ответа, если все элементы различны.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<long long> ans;

    long long current_value = a[0];
    long long current_count = 1;

    for (int i = 1; i < n; i++) {
        if (a[i] == current_value) {
            current_count++;
        } else {
            ans.push_back(current_value);
            ans.push_back(current_count);
            current_value = a[i];
            current_count = 1;
        }
    }

    ans.push_back(current_value);
    ans.push_back(current_count);

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

ans = []

current_value = a[0]
current_count = 1

for i in range(1, n):
    if a[i] == current_value:
        current_count += 1
    else:
        ans.append(str(current_value))
        ans.append(str(current_count))
        current_value = a[i]
        current_count = 1

ans.append(str(current_value))
ans.append(str(current_count))

print(' '.join(ans))