Розв'язок
Позначимо через суму всіх елементів масиву, а через — його максимальний елемент.
Для префікса довжини необхідно, щоб 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();
}