蓝桥杯集训·每日一题 AcWing 3729. 改变数组元素（差分）_acwing3729 题java解法

题目链接：3729.改变数组元素

题意：根据已有的整数数组a，确定空数组v的元素进行操作，并最后输出。具体操作如下：

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

在数组 V尾部插入整数 0（此时数组 V中的元素个数为i），然后将位于数组 V 末尾的 ai 个元素变为 1（也就是从数组 V第i个元素，即最后一个元素，开始的前面的 ai 个元素）

知识点差分，如下图解

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200010],b[200010];
int main(){
    cin>>T;
    while(T--){
        memset(b,0,sizeof(b));//注意初始化 
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]=min(i,a[i]);//此时a[i]表示要更新元素的个数，i 表示数组v中已经有的元素个数 
            //取i,a[i] 两者中的最小 
            
            int l=i-a[i]+1,r=i+1;//把数组v区间 l~r 的元素均变为1 
            b[l]++;b[r]--;
        }
        for(int i=1;i<=n;i++) b[i]+=b[i-1];
        for(int i=1;i<=n;i++){
            if(b[i]>0) cout<<1<<' ';
            else cout<<0<<' ';
        }
        cout<<endl;
    }        
}