蓝桥杯算法提高VIP-分苹果
题目描述
小朋友排成一排，老师给他们分苹果。
小朋友从左到右标号1..N。有M个老师，每次第i个老师会给第Li个到第Ri个，一共Ri-Li+1个小朋友每人发Ci个苹果。
最后老师想知道每个小朋友有多少苹果。
输入格式
第一行两个整数N、M，表示小朋友个数和老师个数。
接下来M行，每行三个整数Li、Ri、Ci，意义如题目表述。
数据规模和约定
100%的数据，N、M≤100 000，1≤Li≤Ri≤N，0≤Ci≤100。
输出格式
一行N个数，第i个数表示第i个小朋友手上的水果。
样例输入
复制
5 3 1 2 1 2 3 2 2 5 3
样例输出
复制
1 6 5 3 3
大佬的思想简直太牛掰了必须记录一下，又是智商被碾压的一天。
面对这类题，一般思想几个循环就可以搞定，但是可想而知复杂度有多高，再者蓝桥杯的题怎么可以几个循环就能够打发的。
参考大佬的差分数组求解。所谓差分数组，就是说假设有两个数组d[i],a[i],d[i]=a[i]-a[i-1],d[0]=a[0],那么d[i]就是a[i]的差分数组，d[i]的前缀和就是a[i],即a[i]=d[i]+d[i-1]+...+d[0];
其基本思想如下：
发苹果的方式是连续的，满足差分数组的要求；
每次发苹果时第l个小朋友会比第l+1个小朋友多c个
第r+1个小朋友又会比第r个小朋友少c个
老师分发完后利用公式x[i]=x[i]+x[i-1]求出每一个小朋友的被分得苹果的个数
import java.util.Scanner;public class Main {public static void main(String []args){Scanner sc=new Scanner(System.in);int m,n;//m为小孩的个数，n为老师的个数m=sc.nextInt();n=sc.nextInt();int l,r,c;//分别为开始小孩位置的标号，结束小孩位置的标号，分发的苹果数int x[]=new int[1000000];//小孩装苹果的数组while(n!=0){l=sc.nextInt();r=sc.nextInt();c=sc.nextInt();x[l]=x[l]+c;x[r+1]=x[r+1]-c;n--;}for(int i=1;i<=m;i++){x[i]=x[i]+x[i-1];System.out.print(x[i]);System.out.print(' ');}}
}
