【Codeforces】1659D Reverse Sort Sum 题解

题目大意

给定一个长度为 $n$ 由 $0, 1$ 组成的序列。然后进行 $n$ 次操作，第 $i$ 次操作会把前 $i$ 个数升序排序。

比如 $0,1,0,1$，4次操作形成的序列分别是 $[0,1,0,1],[0,1,0,1],[0,0,1,1],[0,0,1,1]$，然后每一位分别相加为 $[0,2,2,4]$，设此数组为 $c$。

现在给定数组 $c$，求原来的数组。$1 \le n \le 2 \cdot 10^5$。

题目链接

思路

我们首先来计算有多少个 $1$。每个排序数组 $1$ 的个数不会变，所以我们直接拿 $c$ 数组之和除以 $n$ 即可，设为 $num$。

可以考虑从 $c$ 最后一个位置计算：

• 如果 $c[n] = n$，那么就说明 $a[n] = 1$，且这个 $1$ 不会对前面的答案产生影响。
• 如果 $c[n] = 1$，那么就说明，最后一次排序时，把一个 $1$ 移动到了此位置，所以 $a[n] = 0$。

且我们可以发现，最后一次排序后，数组一定是形如 $0,0,0,0,1,1,1,1$ 的形式，而 $1$ 的数量我们已经算出，所以我们可以直接把数组 $c$ 减去这个序列，这样我们就得到了 $n-1$ 次排序后的 $c$ 数组。这相当于一个子问题，可以按照上述的方法继续求解。

需要注意的是，如果我们算出当前位置是 $0$，那么前面的数中，$1$ 的个数需要减一，否则数量不变。

由于直接暴力相减 $c$ 数组会超时，我们可以提前预处理出每个位置要减去的数，利用 $b[i] - i$ 来表示。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxN = 2e5 + 7;

int T, n, c[maxN], b[maxN], a[maxN];

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        long long sum = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &c[i]);
            sum += c[i];
        }
        memset(b, 0, sizeof b);
        memset(a, 0, sizeof a);
        int num = sum / n, lf = n - num + 1; //lf就是0,0,0,1,1,1,1序列中第一个1的位置
        for(int i  = lf; i <= n; ++i)
            b[i] = n; //第i个位置从第i次排序开始一直到第n次排序时，这个位置都是1
        for(int i = n; i >= 1 && i >= lf; --i) {
            int cur = c[i] - (b[i] - i); //减去第i次排序后，1带来的贡献值
            if(cur == i)
                a[i] = 1;
            else if(cur == 1) {
                a[i] = 0;
                lf--;
                b[lf] = i - 1; //由于这个位置是0，第lf个数在第i-1次排序之后就变成了0
            }
        }
        for(int i = 1; i <= n; ++i)
            printf("%d ", a[i]);
        printf("\n");
    }
    return 0;
}