题目描述
分析
题目要求:
从数组 V 尾部插入整数 0。
将位于数组 V末尾的 ai个元素都变为 1(已经是1的不予理会)。
那么我们可以将ver数组全置为空,运用差分的思想去维护每一次操作,最后的结果是n次操作后的差分结果,只需将大于1的全置为1即可。
模拟
当ai
不为0
时,将后ai
个数全置为1
,如ai=3
时,将后3
个数全置为1
,由于这里每次输入一个ai
,v数组后就补上1个0,所以是将前2个0(因为当前v数组只有2个)全置为1,继续输入ai
,输入的ai为0
时,不需要进行置1
操作,当ai=1
时,ver末尾先补上0,再将最后一个0
置为1
。当ai=3
时,末尾补上0,再将最后3个元素置为1
,如果这3个元素之前已经出现1,则不需要进行修改。
由于差分是将区间内的每个数加上1,所以,会出现将之前为1的元素再加上若干个1即大于1的情况。
这里需要对差分后求缀和的数组进行一个筛选,如果大于等于1,就保留1即可。
0无需做任何操作。
L=i-a+1
ACcode
import java.util.*;
public class Main{
static int N=200010;//2*10的5次方
static int n,a;
static int b[]=new int[N];
public static void main(String []args) {
Scanner in = new Scanner(System.in);
int T=in.nextInt();
while(T-->0) {//T次操作
n=in.nextInt();
Arrays.fill(b, 0);//ver数组初始化全为0
for(int i=1;i<=n;i++) {
a=in.nextInt();
if(a!=0){
int l=Math.max(1,i-a+1);//左边界,确保大于等于1,至少是有一个它本身。
int r=i;//右边界
//差分,将 l-r区间内的数都加上1
b[l]++;
b[r+1]--;
}
}
for(int i=1;i<=n;i++) {
b[i]+=b[i-1];//求一遍前缀和,得到最终答案。
//考虑到差分的次数,会使得部分数字大于1,因此需要将大于1的数全置为1。
//所以用min方法来对输出的b[i]进行处理,将大于1的数全置为1。
System.out.print(Math.min(1, b[i])+" ");
//和b[i]取一个最小值,是1就是1,是0就是0.
}
System.out.println();
}
}
}