改变数组元素

题目描述

给定一个空数组 V 和一个整数数组 a1,a2,…,an。

现在要对数组 V 进行 n 次操作。

第 i 次操作的具体流程如下:

从数组 V 尾部插入整数 0。
将位于数组 V 末尾的 ai 个元素都变为 1(已经是 1 的不予理会)。
注意:

ai 可能为 0,即不做任何改变。
ai 可能大于目前数组 V 所包含的元素个数,此时视为将数组内所有元素变为 1。
请你输出所有操作完成后的数组 V。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

每组数据输出一行结果,表示所有操作完成后的数组 V,数组内元素之间用空格隔开。

数据范围

1≤T≤20000,
1≤n≤2×10^5,
0≤ai≤n,
保证一个测试点内所有 n 的和不超过 2×10^5

输入样例:

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

输出样例:

1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0

思路

方法一:差分(O(N))(N是数组长度)

思路

我们会发现问题可以简化为:给定一个长度为n的0串,然后去修改它中的一些区间变为1。那么我们发现其实有的位置可以被修改很多次,只不过如果已经是1了,那么再修改就不起作用了。所以我们每次,拿到一个值,相当于将一个范围内的所有数字都变为1,于是我们就对修改次数进行差分即可,最后我们求差分数组的前缀和来还原原数组之后,只要是某个位置上的值不是0,那么这个位置就是1。
这里有个小的trick:对于一个非0的值变为1,对于0就是0,有什么简洁的操作吗?答:!!a即可。!会将非零值变为0,将0值变为1。

代码

//差分数组:时间复杂度O(N)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200010;

int b[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        //由于数据范围比较大,我们手动清空b数组
        for(int i = 1; i<=n; i++) b[i] = 0;
        for(int i = 1; i<=n; i++)
        {
            int a;
            cin>>a;
            int l = max(1,i-a+1), r = i;
            b[l]++, b[r+1]--;
        }
        for(int i = 1; i<=n; i++)
        {
            b[i] += b[i-1];
            printf("%d ", !!b[i]);
        }
        cout<<endl;
    }
    return 0;
}

方法二:区间合并(O(NlogN))(N为原始区间的个数)

思路

根据方法一所说,这其实就是将原本一个0串的区多个区间修改为1的过程,只不过这个过程会有重叠,有重叠就意味着时间可能会超。因此,我们可以利用区间合并算法来将重叠的区间进行合并。

区间合并

第一步:按照各个区间的左端点对所有区间进行排序。
第二步:合并区间。

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st = -1, en = -1;
    for(auto & v : segs)
    {
        if(en < v.first)
        {
            if(st != -1) res.push_back({st,en});
            st = v.first, en = v.second;
        }
        else en = max(v.second,en);
    }
    if(st != -1) res.push_back({st,en});
    segs = res;
}

代码

//区间合并 O(NlogN)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 200010;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st = -1, en = -1;
    for(auto & v : segs)
    {
        if(en < v.first)
        {
            if(st != -1) res.push_back({st,en});
            st = v.first, en = v.second;
        }
        else en = max(v.second,en);
    }
    if(st != -1) res.push_back({st,en});
    segs = res;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vector<PII> segs;
        for(int i = 0; i<n; i++)
        {
            int a;
            cin>>a;
            int l = max(0,i-a+1), r = i;
            if(l<=r)
                segs.push_back({l,r});
        }
        // for(auto &t : segs)
        //     cout<<t.first<<" "<<t.second<<endl;
        merge(segs);
        // for(auto &t : segs)
        //     cout<<t.first<<" "<<t.second<<endl;
        vector<int> ans(n);
        for(auto & t: segs)
        {
            for(int i = t.first; i<=t.second; i++)
                ans[i] = 1;
        }
        for(int i = 0; i<n; i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。