CodeForces Global Round 11 A. Avoiding Zero 构造

CodeForces Global Round 11 A. Avoiding Zero 构造

题意

现在你有一个长度为(n)的数组(a)，今需要重新排列数组(a),构造出新的数组(b)，使得对每个(b)的前缀有(sum[i] eq 0)

[1leq n leq 50 \ -50leq a_i leq 50 ]

分析

看见数据范围，竟然在往暴力方向想，回过神来发现其实很显然的构造：

令(tot = sum a_i)

• 若(tot = 0) ,显然不存在
• 若(tot > 0) ,对(a)排序，从大到小输出。显然前缀和是一个递减的序列，但是$sum[0] > 0 $ 且(sum[n - 1] > 0)，故中间都大于0
• 若(tot < 0) ，与上面同理构造即可

代码

int a[55];


void solve() {
    vector<int> v;
    int n = readint();
    int tot = 0;
    for (int i = 0; i < n; i++)
        a[i] = readint(), tot += a[i];
    if (!tot) {
        puts("NO");
        return;
    }
    puts("YES");
    sort(a, a + n);
    if (tot > 0) {
        reverse(a, a + n);
        for (int i = 0; i < n; i++)
            printf("%d ", a[i]);
        puts("");
    }
    else {
        for (int i = 0; i < n; i++)
            printf("%d ", a[i]);
        puts("");
    }
}

int main() {
    int T = readint();
    while (T--)
        solve();
}