蓝桥杯算法提高VIP-分苹果 （C++代码）

解题思路:

言归正传，所谓差分数组，就是说假设有两个数组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];

本题中，发苹果的方式是连续的，那么每次改变的差分数组只有d[l]和d[r+1],连续m次，d[l]加上c，d[r+1]减去c，注意d[r+1]不要超出数组范围，所以我在申请数组d的时候多申请了一个空间。

注意事项:

参考代码:

#include <iostream>
using namespace std;
int main()
{
	int n, m, i, j;
	cin >> n >> m;
	//int *L = new int[m];
	//int *R = new int[m];
	//int *C = new int[m];
	int l, r, c;
	int *child = new int[n + 1];
	int *diff = new int[n + 2];
	child[0] = diff[0] = 0;
	for(i = 0; i < n+1; i++) {
		diff[i] = 0;
	}
	for (i = 0; i < m; i++) {
		cin >> l >> r >> c;
		diff[l] += c;
		diff[r + 1] -= c;
	}
	for (i = 1; i <= n; i++) {
		child[i] = child[i - 1] + diff[i];
		cout << child[i] << " ";
	}
	return 0;
}