Потрібна перестановка#13121

Потрібна перестановка (Розбір)

Розв'язок

Позначимо через суму всіх елементів масиву, а через — його максимальний елемент.

Для префікса довжини необхідно, щоб S\le M. Тому, якщо S>M, відповіді не існує.

Покажемо, що умови S\le M також достатньо.

Якщо всі елементи від'ємні, виведемо їх у довільному порядку. Сума кожного префікса не перевищує його першого елемента, а отже, не перевищує й максимуму на цьому префіксі.

Інакше побудуємо перестановку так: спочатку всі від'ємні елементи, потім один елемент зі значенням , а після нього — решту невід'ємних елементів, включно з нулями.

Для префіксів, які складаються лише з від'ємних елементів, нерівність виконується з тієї самої причини. Після додавання сума префікса не перевищує , і його максимум дорівнює . Усі наступні елементи невід'ємні, тому суми префіксів далі не спадають і не перевищують повної суми S\le M. Отже, всі префікси задовольняють умову.

Таким чином, відповідь існує тоді й лише тоді, коли S\le M.

Складність

Кожен елемент обробляємо сталу кількість разів, тому часова складність , додаткова пам'ять .

Реалізація C++17

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

void solve() {
    int n;
    cin >> n;

    vector<int> neg, pos;
    long long sum = 0;
    int mx = INT_MIN;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        sum += x;
        mx = max(mx, x);
        if (x < 0) neg.push_back(x);
        else pos.push_back(x);
    }

    if (sum > mx) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
    for (int x : neg) cout << x << ' ';

    if (!pos.empty()) {
        for (int i = 0; i < (int)pos.size(); i++) {
            if (pos[i] == mx) {
                swap(pos[0], pos[i]);
                break;
            }
        }
        for (int x : pos) cout << x << ' ';
    }
    cout << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}