CF1852B Imbalanced Arrays

CF1852B Imbalanced Arrays 题解

题目大意

对于一个给定的长度为 $n$ 的数组 $A$，定义一个长度为 $n$ 的数组 $B$ 是不平衡的当且仅当以下全部条件满足：

• $-n \leq B_{i} \leq n$ 且 $B_{i} \ne 0$。即每个数在 $[-n,n]$ 内且不为 $0$。

• $\forall i,j \in [1,n], B_{i} + B_{j} \neq 0$。即数组内不存在一对相反数。

• $\forall i \in [1,n], \sum_{j = 1}^{n} [ \left (B_{i} + B_{j} \right) > 0] = A_{i}$。即对于任意的 $i$，数组中与 $B_{i}$ 和大于 $0$ 的数的个数恰好为 $A_{i}$。注意：这里需要计算本身。也即 $i$ 与 $j$ 可以相等。

请构造长度为 $n$ 的不平衡序列。

思路

一个很重要的性质是，一个数列中必然存在一个绝对值最大的数，如果它是正的，那么它对应的 $a_i$ 一定是数列的长度，如果它是负的，那么它对应的 $a_i$ 一定是 $0$。

由此，我们每次找数列 $a$ 中等于数列长度的项或值为 $0$ 的项，并确定它们的值，然后更新数列 $a$ 即可。

如果在处理过程中数列 $a$ 不存在等于数列长度的项或值为 $0$ 的项或两种都存在，则无法进行构造。

这个过程可以对 $a$ 排序后用双指针来处理。

代码

int n, b[maxN + 5];
struct node {
    int val, id;
} a[maxN + 5];
void solve() {
    cin >> n;
    rep(i, 1, n) {
        b[i] = 0;
        cin >> a[i].val;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, [](node x, node y) { return x.val < y.val; });
    int l = 1, r = n, cnt = 0, curr_n = n;
    while (l < r) {
        bool fl[2] = {(a[l].val - cnt == 0), (a[r].val - cnt == r - l + 1)};
        int l0 = l, r0 = r;
        if (fl[0] ^ fl[1]) {
            if (fl[0]) {
                while (a[l].val - cnt == 0) {
                    b[a[l].id] = -curr_n, l++;
                }
            } else {
                while (a[r].val - cnt == curr_n) {
                    b[a[r].id] = curr_n, r--;
                }
                cnt += r0 - r;
            }
            curr_n = r - l + 1;
        } else {
            cout << "NO\n";
            return;
        }
    }
    if (l == r && !b[a[l].id]) {
        if (a[l].val - cnt == 0) {
            b[a[l].id] = -1;
        } else if (a[l].val - cnt == 1) {
            b[a[l].id] = 1;
        } else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    rep(i, 1, n) cout << b[i] << " ";
    cout << endl;
}