【CF1798D】Shocking Arrangement

一扶苏一 · 2023-03-30 23:17:23 · 题解

【CF1798D】Shocking Arrangement

Description

给出一个长度为 n 的数列 a，满足 \sum_{i = 1}^n a_i = 0。

你需要重排这个数列，使得重排后满足

多组数据，n 之和不超过 3 \times 10^5，|a_i| \leq 10^9。

Analysis

整蛊题。

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

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

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

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

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

而任何区间的和都可以写成两个前缀和相减的形式。设 s_i 是长度为 i 的前缀和，则 |\sum_{i = l}^r a_i| = |s_r - s_{l}| \leq \max a_i - \min a_i。任何区间都满足这个限制，自然区间和绝对值的最大值也满足这个限制。正确性得证。

Code

写代码时把正数和非负数分别排了个序，现在看起来似乎是不必要的。

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

int T;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (std::cin >> T; T; --T) {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b, c;
    std::generate(a.begin(), a.end(), []() { int x; std::cin >> x; return x; });
    if (*std::max_element(a.begin(), a.end()) == 0) {
      std::cout << "No\n";
      continue;
    }
    std::cout << "Yes\n";
    for (auto i : a) 
      if (i < 0) b.push_back(i);
      else c.push_back(i);
    std::sort(b.begin(), b.end());
    std::sort(c.begin(), c.end(), std::greater<int>());
    int sum = 0;
    for (int i = 1, j = 0, k = 0; i <= n; ++i) {
      if (sum >= 0 && j < b.size()) {
        std::cout << b[j] << ' ';
        sum += b[j++];
      } else {
        std::cout << c[k] << ' ';
        sum += c[k++];
      }
    }
    std::cout << '\n';
  }
}