Построение массива

Задача на кучу отрезков с жадным выбором лучшего

Дан массив длины n из нулей. На каждом из n шагов нужно:

1. найти самый длинный подотрезок, состоящий из нулей; при равенстве длин — самый левый;
2. в серединную клетку этого отрезка записать номер шага i. Для отрезка чётной длины середина — левая из двух центральных.

После n шагов вывести получившийся массив. В условии сказано, что ответ существует и единственен.

Пример для n = 5 из условия — массив превращается в [2, 4, 1, 3, 5].

Посмотрим внимательно на то, что нам нужно на каждом шаге:

• взять лучший элемент (самый длинный/левый отрезок) — это приоритет;
• удалить его из рассмотрения;
• добавить новые кандидаты — две половинки оставшихся нулей.

Это буквально описание приоритетной очереди. Каждый отрезок нулей — это один элемент кучи. Когда мы ставим число в середину отрезка [l; r], этот отрезок разбивается на два: [l; m−1] и [m+1; r], которые мы кладём обратно в кучу. Через n шагов мы сделаем n операций pop и около 2n операций push — итого O(n log n).

Каждый отрезок — пара (длина, левая граница). Длина нужна для приоритета, левая граница — для разрешения ничьих. По правой границе можно не хранить: она выводится как l + length − 1.

В итоге в Python ключ кучи — тройка (−length, l, r). В C++ для priority_queue (max-heap) используем (length, −l, r): большая длина выигрывает, при равной длине выигрывает больший −l, то есть меньший l.

В условии индексация с 1, и там различаются формулы для чётной и нечётной длины. Если считать с 0, формула одна для всех случаев:

# Независимо от чётности длины:
m = (l + r) // 2

Для нечётной длины это настоящий центр, для чётной — левый из двух центральных. Именно это и нужно в условии.

1. Положить в кучу исходный отрезок [0; n−1] длины n.
2. Для i от 1 до n: достать верх кучи — отрезок [l; r].
3. Вычислить m = (l + r) / 2 и записать a[m] = i.
4. Если левая половинка [l; m−1] непустая — положить её в кучу. То же для правой [m+1; r].

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

Обрати внимание, как на ничьих побеждает самый левый отрезок: после первой постановки в центр n = 5 получатся два отрезка длины 2, и алгоритм берёт сначала левый [0; 1], только потом правый [3; 4].

import heapq
import sys

input = sys.stdin.readline

def solve(n):
    a = [0] * n
    # (-length, l, r) — минимум даёт максимальную длину,
    # при равенстве — меньший l
    heap = [(-n, 0, n - 1)]
    for i in range(1, n + 1):
        neg_len, l, r = heapq.heappop(heap)
        m = (l + r) // 2
        a[m] = i
        if l <= m - 1:
            heapq.heappush(heap, (-(m - l), l, m - 1))
        if m + 1 <= r:
            heapq.heappush(heap, (-(r - m), m + 1, r))
    return a

t = int(input())
out = []
for _ in range(t):
    n = int(input())
    out.append(' '.join(map(str, solve(n))))
print('\n'.join(out))

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n, 0);

        // (length, -l, r) — max-heap выдаст наибольшую длину,
        // при равенстве — наибольший (-l), то есть наименьший l
        priority_queue<tuple<int, int, int>> pq;
        pq.push({n, 0, n - 1});

        for (int i = 1; i <= n; i++) {
            auto [len, neg_l, r] = pq.top(); pq.pop();
            int l = -neg_l;
            int m = (l + r) / 2;
            a[m] = i;
            if (l <= m - 1) {
                pq.push({m - l, -l, m - 1});
            }
            if (m + 1 <= r) {
                pq.push({r - m, -(m + 1), r});
            }
        }

        for (int x : a) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

За один тест выполняется ровно n операций pop и не более 2n операций push (каждое разбиение рождает не более двух новых отрезков, иногда один или ноль, когда получается пустая половинка). Итого O(n log n) на тест и O(Σn · log(maxn)) на все тесты — укладывается в лимит с большим запасом.

По памяти — O(n) на массив и кучу, никаких проблем.

Если при равной длине отрезков взять произвольный (а не самый левый), ответ поменяется. В Python если положить в кучу (-length,) без второй компоненты — при равных длинах порядок определит heapq по своему внутреннему счётчику, а это фактически случайно. Нужно обязательно добавить l как вторую компоненту ключа.

В 1-based условии середина чётного отрезка — это (l + r − 1) / 2, а не (l + r + 1) / 2. То есть левый из двух центральных, не правый. В 0-based это естественным образом даёт (l + r) // 2 — никаких дополнительных проверок.

Когда отрезок длины 1, после постановки он превращается в две пустые половинки — их не надо класть обратно в кучу. Поэтому проверки l ≤ m − 1 и m + 1 ≤ r обязательны.

При t = 10⁴ вызовов input() чистый Python может не успеть только на чтении. Ставим sys.stdin.readline и выводим всё одним print через '\n'.join — это даёт многократное ускорение.