蓝桥杯--算法提高--VIP--分苹果题目（差分数组）

1. 问题描述：

小朋友排成一排，老师给他们分苹果。 
小朋友从左到右标号1..N。有M个老师，每次第i个老师会给第Li个到第Ri个，一共Ri-Li+1个小朋友每人发Ci个苹果。 
最后老师想知道每个小朋友有多少苹果。 
数据规模和约定 
100%的数据，N、M≤100  000，1≤Li≤Ri≤N，0≤Ci≤100。 

输入

第一行两个整数N、M，表示小朋友个数和老师个数。 
接下来M行，每行三个整数Li、Ri、Ci，意义如题目表述。

输出

一行N个数，第i个数表示第i个小朋友手上的水果。

样例输入

5 3

1 2 1

2 3 2

2 5 3

样例输出

1 6 5 3 3

2. 思路分析：

① 分析题目可以知道这道题目其实是一个区间上点的的频次问题，弄清楚考察的点之后我们可以想到使用差分数组的思路来实现，首先我们需要处理输入数据的问题，将输入的数据放到对应的变量中，因为使用的是python语言，所以可以声明一个名为fre的List[int]列表（与java或者是c++的数组是类似的）来记录当前位置出现频次，这里累加的频次不是1，而是题目中给出的当前小朋友的苹果数量，核心处理的是fre列表：我们需要在当前区间起点的位置累加上c[i]，在当前区间终点的下一个位置减去c[i]，这样最后我们对fre列表的当前位置累加上前一个位置的值表示的是当前位置能够分到的苹果的数目了

② 这道题目与力扣中的1589 所有排列中的最大和的题目本质上是类似的，力扣中的累加的次数是1，这里累加的是c[i], 两道题目在细节的处理有点不同，但是可以对照着理解

3. 代码如下：

import sys
from typing import List


class Solution:
    def solve(self, N: int, M: int, Li: List[int], Ri: List[int], Ci: List[int]):
        fre = [0] * (N + 2)
        for i in range(M):
            fre[Li[i]] += Ci[i]
            fre[Ri[i] + 1] -= Ci[i]
        fre.pop()
        for i in range(1, N + 1):
            fre[i] += fre[i - 1]
        fre.pop(0)
        return fre


if __name__ == '__main__':
    # 5 3
    # 1 2 1
    # 2 3 2
    # 2 5 3
    # 一行读入若干个数字
    N, M = map(int, sys.stdin.readline().split())
    Li, Ri, Ci = list(), list(), list()
    for i in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        Li.append(a)
        Ri.append(b)
        Ci.append(c)
    # print(M, N)
    # print(Li, Ri, Ci)
    res = Solution().solve(N, M, Li, Ri, Ci)
    for i in res:
        print(i, end=" ")