cf1659D

题目大意

给定一个长度为\(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*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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/05/13/cf1659D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！