采用差分方法的python解法
- 使用差分数组的意义就在于记录改变次数,改变过就+1
代码过程如下:
def insert(b,l,r,c):
b[l]+=c
b[r+1]-=c
T = int(input())
while T>0: #操作次数
T-=1
n = int(input())
a = [0]+list(map(int,input().split()))#原数组
b = [0]*(n+10) #差分数组
for i in range(n+1):
if a[i]==0:#若为0,不需要改变
continue
else:
l = max(0,i-a[i]+1)
r = i
insert(b,l,r,1)
for i in range(1,n+1):
b[i]+=b[i-1] #将差分数组恢复
for i in range(1,n+1):
if b[i]!=0: #若数组非0,即被操作过,输出1即可
print(1,end=" ")
else:
print(0,end=" ")
print()