A Suitable Rearrangement#13121

A Suitable Rearrangement (Editorial)

Solution

Let be the sum of all elements of the array, and let be its maximum element.

For the prefix of length , we must have S\le M. Therefore, if S>M, no valid rearrangement exists.

We will show that the condition S\le M is also sufficient.

If all elements are negative, we can output them in any order. The sum of each prefix does not exceed its first element, and therefore does not exceed the maximum element of that prefix.

Otherwise, construct the rearrangement as follows: first place all negative elements, then one element equal to , and finally all remaining non-negative elements, including zeros.

For prefixes consisting only of negative elements, the inequality holds for the same reason as before. After adding , the prefix sum does not exceed , and its maximum is equal to . All subsequent elements are non-negative, so the prefix sums never decrease and cannot exceed the total sum S\le M. Thus, every prefix satisfies the required condition.

Therefore, a valid rearrangement exists if and only if S\le M.

Complexity

Each element is processed a constant number of times, so the time complexity is and the auxiliary space complexity is .

C++17 Implementation

#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();
}