【构造】CF1798 D

超、凢脫俗 2024-03-23 20:15 92阅读 0赞

[Problem - D - Codeforces][]

题意：

![ee9f61a4f71440ea8d521c072445781b.png][]

思路：

首先如果 a 全是 00，那么显然无解。

否则考虑从左到右构造新数列，维护新数列的前缀和 s。

*  如果 s≥0，则在剩余未加入的数中随便选择一个非正数添加到新数列末尾。
 *  如果 s<0，则在剩余未加入的数中随便选择一个负数添加到新数列末尾。

因为保证了数列之和为 0，所以当 s≥0 时，你总能找到还没添加的非正数，同理第二种情况你也总能找到未添加的正数。

考虑这样构造的正确性：注意到 min ai ≤ s ≤ max ai。这是因为每次总会添加一个和 s 异号的数。当 s≥0 时，能找到的最小数也是 min ai，则新的前缀和 's′ 满足 s′≥s+min ai。类似可以证明s≤max ai。

而任何区间的和都可以写成两个前缀和相减的形式。设 si 是长度为 i 的前缀和，则 ∣∑i=lrai∣=∣sr−sl∣≤max ai−min ai。任何区间都满足这个限制，自然区间和绝对值的最大值也满足这个限制。正确性得证。

Code：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 1e9 + 7;
    
    void solve() {
        int n;
        std::cin >> n;
        
        std::vector<int> a(n);
        int ok = 0;
        for (int i = 0; i < n; i ++) {
            std::cin >> a[i];
            if (a[i] != 0) ok = 1;
        }
    
        if (!ok) {
            std::cout << "No" << "\n";
            return;
        }
        std::cout << "Yes" << "\n";
    
        int l = 0, r = n - 1;
        i64 s = 0;
        std::sort(a.begin(), a.end());
    
        std::vector<int> ans;
        while(l <= r) {
            if (s <= 0) {
                s += a[r];
                ans.push_back(a[r --]);
            }else {
                s += a[l];
                ans.push_back(a[l ++]);
            }
        }
        for (int i = 0; i < ans.size(); i ++) {
            std::cout << ans[i] << " \n" [i == ans.size() - 1];
        }
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        std::cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1798/problem/D
[ee9f61a4f71440ea8d521c072445781b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7bffd027748847df9d9ea8611fbb6159.png