昨天满课了没有更新，今天下午有空去做了一下，今天的知识点是差分数组
1.题目
https://www.acwing.com/problem/content/3732/
2.思路分析
构建差分数组，对每次数据进行判断，如果是0，那么不需要操作，直接结束
如果大于 当前数组所包含的元素个数，那么将目前数组所有位置的数都+1
如果不大于，那么对数组从i - x + 1的位置到i的位置上的数+1
3.Ac代码
import java.io.*; import java.util.Arrays; public class Main { static int N=2*100010; static int []arr=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int T=Integer.parseInt(br.readLine()); while (T-->0){ Arrays.fill(arr,0); //每次都要重新归零 int n=Integer.parseInt(br.readLine()); String []s=br.readLine().split(" "); for (int i = 1; i <=n; i++) { int t=Integer.parseInt(s[i-1]); if(t==0) continue;//a[i]为0就不进行任何操作 if(t>=i) add(1,i);//a[i]大于等于目前的数组的长度就相当于从1到i做一个操作 else add(i-t+1,i);//末尾a[i]个数，就是正序的第i - a[i] + 1的位置 } for (int i=1;i<=n;i++) arr[i]+=arr[i-1]; //前缀和一下 for (int i=1;i<=n;i++){ //最后的前缀和数组中如果是0就表示没有发生0换1的情况，不为0就是发生过0换1的情况 if(arr[i]!=0) System.out.print("1 "); else System.out.print("0 "); } System.out.println(); } } private static void add(int i, int j) { arr[i]+=1; arr[j+1]-=1; } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
