Решение задачи Отсортированные разности соседних с Codeforces

Без пояснения   Просмотров: 54


У вас есть массив из n чисел a1,a2,…,an.

Переставьте эти числа так, чтобы они удовлетворяли |a1−a2|≤|a2−a3|≤…≤|an−1−an|, где |x| обозначает абсолютное значение x. Гарантируется, что для данных ограничений всегда можно найти такую перестановку.

Обратите внимание, что элементы в a не обязательно попарно различны. Другими словами, некоторые элементы a могут быть одинаковыми.

Вы должны ответить на t независимых тестовых случаев.

Код

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll TN = 1;

int solution() {
    ll n;
    cin >> n;
    vector <ll> a(n);
    for (ll i = 0; i<n; ++i) {
        cin >> a[i];
    } sort(a.begin(), a.end());
    vector <ll> ans(n);
    ll j = n-1;
    for (ll i = n-2; i>=0; i-=2) {
        ans[i] = a[j];
        --j;
    } j = 0;
    for (ll i = n-1; i>=0; i-=2) {
        ans[i] = a[j];
        ++j;
    } for (ll i = 0; i<n; ++i) {
        cout << ans[i] << " ";
    } cout << "\n";
    return 0;
}

int main() {
    cin >> TN;
    for (ll i = 0; i<TN; ++i) solution();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться