526互联

【题解】Imbalanced Arrays - Codeforces 1852B

发布时间 2023-07-24 20:29:32作者: purinliang

出处： Codeforces Round 887

链接： https://codeforces.com/problemset/problem/1852/B


题目大意：

给定一个包含 \(n\) 个非负整数的频次序列 \(f\) 。

构造任意一个等长的整数序列 \(b\) ，要求
① \(b \in [-n, n]\) but $b \neq 0 $
② \(b\) 中不存在相反数
③ 对于每个坐标 \(i\) ，序列中的（可以和 \(i\) 重复的）坐标 \(j\) ，且能满足 \(b_i+b_j>0\) 的 \(j\) 的个数刚好为 \(f_i\) 频次
说明不存在这样的 \(b\) 满足这个条件。

约束： \(1\leq n \leq 10^5\) ， \(0\leq f_i \leq 10^5\) 。


解题思路：

  1. 先观察有什么规律

    构造 \(b\) 序列时的前两个要求，其实变相说明了只能从 \(\{-n,n\}, \{-n+1, n-1\}, \dots, \{-1, 1\}\) 里面每组挑选至多一个作为值出现。

    引理1：假设要选出 \(6\) 个不同的值，则选出的值必定满足以下两种模式其中之一：① \(-6,-4,-2,1,3,5\) 或者 \(-5,-3,-1,2,4,6\) 。证明似乎是显然的，因为构造 \(b\) 序列时的前两个要求导致的。

    引理2：假如要选出 \(n\) 个值，并且运行一部分的值重复，得到的序列依然满足上一条引理约束的模式。也就是对于 \(0\) 的同一侧，距离必定相差为 \(2\) ，且 \(0\) 的两侧的奇偶值必定相反，且一定从 \(-2,-1,1,2\) 这样的值开始。首先先证明为什么距离必定是 \(2\) ，因为假如距离大于 \(2\) 则中间可以插入另一个相反数，而几个连续的相反数之间对于是否和对侧的相反数加起来超过 \(0\) 是没有变化的，也就是说他们是等价的。比如对于 \(-6,-2\) 来说， \(3,4,5\) 其实是完全等价的。没有意义，可以约简为 \(3\) ，进而把 \(-6\) 约简为 \(-4\) ，转换成上一条引理约束的形式。

    引理3：越大的频次，对应的 \(b\) 值应该越大。这是一个显然的单调性。

    引理4：相同的频次，对应相同的 \(b\) 值。这个没有那么明显，但用反证法去看也是一样的。如果某个相同的频次 \(f\) 对应的 \(b\) 值不同，那么这两个 \(b\) 值中间不能插入其他的相反数，否则会导致频次至少相差 \(1\) ，矛盾。

    引理5：相同的 \(b\) 值，对应相同的频次。这个很明显，因为 \(b\) 序列确定了之后，是跟位置完全无关的，所以一定会得到相同的频次。

    根据上面的引理，可以知道一个约简的办法，就是先数一数有多少种不同的频次，记为 \(cntF\) 种，那么只需要验证引理1中的两个模式的 \(b\) 序列即可知道是否有解，其他的模式一定完全等价于这两个模式。并且由于引理3和引理4，可以知道每一个 \(b\) 值是和某一个频次唯一一一对应的。

  2. 算法和复杂度细节

    既然知道了构造的方法是唯一（唯二？）的，那么只需要编程就行了。

    由于引理3，所以要对频次进行一个排序（同时要保留原本输入的顺序用以输出，可以用常见的 pair<int, int> 和 sort 搞定。），排序之后就可以贪心去给每个频次分配一个 \(b\) 值。复杂度为 \(O(nlogn)\) 。

    构造出 \(b\) 序列之后，在验证频次是否合理的过程中，也可以使用双指针等方法进行加速，实在偷懒可以用一个树状数组啥的。复杂度为 \(O(n)\) 。

    构造出第一个 \(b\) 序列之后，再构造另一个重新计算一次，注意这里要特别处理经过 \(0\) 的情况。

点击查看代码 
int n;
pii f[200005];
int b[200005];
int sortB[200005];

bool check (int cntF) {
    if (cntF == 0) {
        // 非常重要，要避开 0 ！！！
        --cntF;
    }
    int curB = cntF;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && f[i].first != f[i - 1].first) {
            // b 序列中， 0 的同一侧，相邻的值差为 2
            curB -= 2;
            if (curB == 0 || curB == -1) {
                // 如果 -2 之后越过了0，说明之前是 2 或者 1，这里要避开 0 或者 -1
                --curB;
            }
        }
        b[f[i].second] = curB;
        sortB[i] = curB;
    }

    int r = n;  // 用双指针法计算 b[i] + b[j] > 0 的频次
    for (int i = 1; i <= n; ++i) {
        while (r > 0 && sortB[r] + sortB[i] <= 0) {
            --r;
        }
        // sortB[r] + sort[i] > 0
        if (f[i].first != r) {
            return false;
        }
    }
    return true;
}

void solve() {
    RD (n);
    for (int i = 1; i <= n; ++i) {
        RD (f[i].first);
        f[i].second = i;
    }
    sort (f + 1, f + 1 + n);
    reverse (f + 1, f + 1 + n); // 套引理3，从大到小进行构造

    int cntF = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == 1 || f[i].first != f[i - 1].first) {
            ++cntF; // 计算一共有多少种不同的频次，用于套引理1进行构造
        }
    }

    if (check (cntF) || check (cntF - 1)) {
        // 对于偶数：
        // 6, 4, 2, -1, -3, -5
        // 5, 3, 1, -2, -4, -6
        // 对于奇数：
        // 7, 5, 3, 1, -2, -4, -6
        // 6, 4, 2, -1, -3, -5, -7
        puts ("YES");
        WTN (b, n);
    } else {
        puts ("NO");
    }
}
  1. 用此算法计算出的 \(b\) 是绝对值之和最小的 \(b\) ，与官方题解的答案略有不同。