Реши задание на изображении

Краткий ответ: задачу удобно решать с помощью кучи отрезков между уже выбранными номерами. Сложность — \(O(N\log N)\), память — \(O(N)\).

Пусть pos[x] — позиция номера \(x\) в старом списке. Чем меньше pos[x], тем раньше номер встречается в старом списке.

Идея

После выбора нескольких номеров все ещё не выбранные номера образуют промежутки.

Для внутреннего промежутка \((l,r)\):

\[ d(x)=\min(x-l,\ r-x). \]

Максимум достигается в середине:

\[ d=\left\lfloor\frac{r-l}{2}\right\rfloor. \]

Возможные центральные номера:

x1 = l + d
x2 = r - d

Если их два, оставляем тот, у которого меньше pos.

Для крайних промежутков:

• \((0,r)\): лучший номер — \(1\), расстояние \(r-1\);
• \((l,N+1)\): лучший номер — \(N\), расстояние \(N-l\).

В куче сначала выбираем промежуток с максимальным расстоянием, а при равенстве — номер, который раньше находится в старом списке. После выбора номера промежуток разделяется на два.

Решение на C++17

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

struct Gap {
    int l, r;          // границы промежутка
    int candidate;     // лучший номер в промежутке
    int distance;      // его минимальное расстояние
    int oldPosition;   // позиция в старом списке
};

struct Compare {
    bool operator()(const Gap& a, const Gap& b) const {
        if (a.distance != b.distance) {
            return a.distance < b.distance; // большее расстояние выше
        }
        return a.oldPosition > b.oldPosition; // раньше в старом списке выше
    }
};

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

    int N;
    cin >> N;

    vector<int> a(N);
    vector<int> pos(N + 1);

    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    auto makeGap = [&](int l, int r) -> Gap {
        int candidate;
        int distance;

        if (l == 0) {
            // Крайний левый промежуток
            candidate = 1;
            distance = r - 1;
        } else if (r == N + 1) {
            // Крайний правый промежуток
            candidate = N;
            distance = N - l;
        } else {
            // Внутренний промежуток
            int len = r - l;
            distance = len / 2;

            int x1 = l + distance;
            int x2 = r - distance;

            if (pos[x1] <= pos[x2]) {
                candidate = x1;
            } else {
                candidate = x2;
            }
        }

        return {l, r, candidate, distance, pos[candidate]};
    };

    priority_queue<Gap, vector<Gap>, Compare> heap;
    vector<int> answer;
    answer.reserve(N);

    // Первый номер фиксирован условием
    int first = a[0];
    answer.push_back(first);

    if (first > 1) {
        heap.push(makeGap(0, first));
    }
    if (first < N) {
        heap.push(makeGap(first, N + 1));
    }

    while (!heap.empty()) {
        Gap current = heap.top();
        heap.pop();

        int x = current.candidate;
        answer.push_back(x);

        // Левая часть промежутка
        if (x - current.l > 1) {
            heap.push(makeGap(current.l, x));
        }

        // Правая часть промежутка
        if (current.r - x > 1) {
            heap.push(makeGap(x, current.r));
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << answer[i] << (i + 1 == N ? '\n' : ' ');
    }

    return 0;
}

Почему решение корректно:

1. В каждом промежутке хранятся все ещё не выбранные номера.
2. Для каждого промежутка вычисляется номер с максимальным расстоянием до выбранных.
3. Куча выбирает лучший номер среди всех промежутков.
4. При одинаковом расстоянии используется позиция в исходном списке.
5. После выбора промежуток разделяется, поэтому каждый номер выводится ровно один раз.