算法提高 分苹果
时间限制：1.0s 内存限制：256.0MB

问题描述
　　小朋友排成一排，老师给他们分苹果。
　　小朋友从左到右标号1…N。有M个老师，每次第i个老师会给第Li个到第Ri个，一共Ri-Li+1个小朋友每人发Ci个苹果。
　　最后老师想知道每个小朋友有多少苹果。
输入格式
　　第一行两个整数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
数据规模和约定
　　40%的数据，N、M≤1 000。
　　100%的数据，N、M≤100 000，1≤Li≤Ri≤N，0≤Ci≤100。

第一种方法

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
	int n, m;
	cin >> n >> m;
	int *a = new int[n];
	for (int i = 0; i < n; i++)
	{
		a[i] = 0;
	}
	while (m--)
	{
		int li, ri, ci;
		cin >> li >> ri >> ci;
		for (int i = 0; i < n; i++)
		{
			if (li - 1 <= i&&i <= ri - 1)
			{
				a[i] += ci;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	} 
	system("pause");
	return 0;
}

这么写 结果很明显，一半的用例超时。

第二种方法，"//"标记处是关键！！！！

#include<stdio.h>
int a[100005];
 
int main()
{
    int n,m,i,l,r,c;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&c);
        a[r]+=c;//
        a[l-1]-=c;//
    }
    for(i=n-1;i>=1;i--)
        a[i]+=a[i+1];//
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}